Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, ...

learn more… | top users | synonyms

5
votes
0answers
141 views

Solving polynomial equations modulo $1$

Let $P\in \mathbb{R}\lbrack x\rbrack$ be given. (In practice, the coefficients could be given as, say, decimals to sufficient precision.) Let $M\geq 1$, and let $I$ be an interval in ...
0
votes
0answers
20 views

combinations of $k$ values that equals a sum within a sequence of ordered linear values [closed]

exemple : subset size : $k = 2$ (can be $> 2$) Sum to find : 11 sequence : $ 1,2,3,4,5,6,7,8,9,10, \dotsc, n$ => result of $k$-size [1,10] [2,9] [3,8] [4,7] .... Any optimized, dichotomic ...
0
votes
0answers
39 views

Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
0
votes
1answer
23 views
+50

How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparce rate matrix?

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...
4
votes
0answers
121 views
+50

Optimal instructions for the modular construction of rectlinear Lego structures

Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
9
votes
0answers
86 views

Factorisation in $\mathbb{N}[X]$?

Do we know an efficient algorithm to factorise in $\mathbb{N}[X]$ ? One way to do factorisation in $\mathbb{N}[X]$ is to use an algorithm to factorise in $\mathbb{Z}[X]$ and to combine some factor to ...
5
votes
2answers
778 views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm(). According to ...
0
votes
3answers
99 views

How to do a clockwise ordering of a planar graph in order to define its faces?

I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no ...
0
votes
0answers
14 views

Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...
7
votes
1answer
283 views

Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
0
votes
2answers
88 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...
1
vote
0answers
76 views

maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
3
votes
0answers
50 views

Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
2
votes
2answers
295 views

Irreducible algebraic sets via irreducible polynomials

There are many results about irreducible polynomials over finite fields: we know a cardinality of all irreducible polynomials with given degree, we know explicit examples of irreducible polynomials, ...
4
votes
1answer
292 views

an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
3
votes
0answers
358 views

Finding the number of rational points effectively

Consider $\# P$ and $\oplus P$. There is a $\# P$-hard problem: to find number of rational solutions of a system of polynomial equations over $\mathbb{F}_2$. The corresponding $\oplus P$-hard ...
1
vote
2answers
49 views

Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution ...
1
vote
1answer
55 views

Is there analogs of perlin noise algorithm?

I want to create procedure generated map, but all resources that I found talks about using of "perlin noise" algorithm. Maybe better (higher perfomance, more realistic terrain generation) analogs ...
3
votes
1answer
88 views

A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
7
votes
1answer
91 views

Fast Fourier Transforms for non-trigonometric bases

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
2
votes
0answers
39 views

smallest ball enclosing one point of each color

I have a set of colored points (say 10 colors with 50 points of each color) in a 100-dimensional space. I want to choose one point of each color so that the 10 points are as close to each other as ...
12
votes
2answers
207 views

Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
0
votes
0answers
33 views

Comparing product of positive affine functions over integers

Problem Let $f_i: \mathbb Z^n \mapsto \mathbb Z$ and $g_i: \mathbb Z^n \mapsto \mathbb Z$ affine functions and $\mathcal D \subseteq \mathbb Z^n$ a set on which they are all positive. Let $P$ and $Q$ ...
7
votes
3answers
292 views

A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
3
votes
0answers
85 views

State of the art for univariate complex polynomials factorization with algebraic coefficients

Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$. ...
8
votes
1answer
286 views

How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$. Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting ...
4
votes
2answers
200 views

Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...
3
votes
1answer
210 views

Periodic strings

I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end ...
3
votes
2answers
98 views

Algorithms for Sorting Subset Sums

In this question the number of unique sortings has been discussed. As a follow-up, I would like to know, whether the problem of sorting the sequence of subset sums has ever been studied. There ...
4
votes
0answers
95 views

How to enumerate a discrete group of matrices by their Frobenius norm?

Suppose I have a discrete group $G<\mathrm{SL}_2(\mathbb{C})$, and it is finitely generated by some known generators. That is, $G=\langle g_1,\dots,g_n\rangle$. The Frobenius norm of a matrix ...
3
votes
0answers
62 views

Algorithm to calculate moments of uniform distribution on convex polyhedra

There is system of linear inequalities $$ Ax \leq K, $$ $$ x\geq a, x\leq b. $$ $A$ is $(n\times m)$-matrix, where $n\approx 100$ and $m\approx 10000$, $rank(A)=n$. Suppose that on set of solutions ...
1
vote
0answers
163 views

“Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
0
votes
0answers
46 views

Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere

Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
1
vote
0answers
46 views

Expected number of forward jumps to reach a given quantile of a rv [closed]

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...
0
votes
1answer
136 views

Find special elliptic curves from j-invariant

Let $E$ be the elliptic curve defined over $GF(p)$ and $j$ be j-invariant of $E$, where $p$ is a big prime number. Also suppose $l$ be small prime number (for example $l<5000$) and $\#E$ denote ...
1
vote
0answers
40 views

Calculating a Combinatorial Generalization of Planar Convex Hulls

In this question I have suggested a generalization of the notion of a set of points in the Euclidean plane being in convex configuration to the set of vertices of symmetric weighted graphs via ...
3
votes
1answer
63 views

Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...
0
votes
0answers
68 views

Algebraic operations with memory hardness properties

In cryptography, there are password hash functions like scrypt and argon2 for which the fastest known algorithms employ large ...
2
votes
1answer
72 views

Area of an irregular, n-sided, non-intersecting (edges) polygon algorithm

I need to generate an irregular, n-sided polygon of non-intersecting edges (n= 200, for example) with the smallest area possible. The position of the vertex is random and I've tried designing a couple ...
-1
votes
1answer
60 views

Computing the inverse of a Cholesky decomposition [closed]

I have chol(A) and I would like chol(A^-1). One way to do this is to construct the inverse positive definite symmetric matrix and then take its Cholesky decomposition (with Dpotri and Dpotrf for ...
2
votes
1answer
103 views

Minimal Support Solutions of a Linear System (Dissertation)

For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times ...
1
vote
2answers
58 views

Maximal Minimum Weight DAGs

In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...
6
votes
0answers
180 views

Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$ It is NP-hard to compute $S_M$ exactly I believe by applying the ...
3
votes
1answer
198 views

Polynomial factoring over finite fields

What is known in general about the complexity of factoring polynomials over finite fields? For instance given $\Bbb F_q$ where $q=p^n$ and total degree $d$ polynomial in $m$ variables what can we say ...
2
votes
0answers
107 views

Detecting Negative Cycles in Undirected Graphs

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...
2
votes
0answers
51 views

Is there a name for this variant of the MST and the TSP?

Suppose I am given a weighted graph $G$ that contains a "start vertex" $v_0$, and my goal is to construct a set of paths that all originate at $v_0$ and touch all of the vertices of $G$, with as ...
9
votes
1answer
185 views

Exact determinant of a circulant matrix

The wikipedia gives us a formula for the determinant of a circulant matrix. That is: $$\mathrm{det}(C) = \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \dots + c_1\omega_j^{n-1})= ...
3
votes
0answers
79 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
2
votes
1answer
105 views

Does anyone have the correct link to treewidth.com?

Several posts (and this) on StackExchange sites like MO have some link-rot. For example, I've been looking into tree decomposition and keep coming across references to treewidth.com, but the link ...
3
votes
0answers
22 views

Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function. OBDD is a DAG with two sinks $0,1$. The size of the BDD is number ...