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

7
votes
1answer
249 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
0answers
33 views

how to measure a bidrectional relationship effect on third variable [on hold]

Sorry that my question was unclear: I decide to determine if there is a relationship between two variables (gross national income, X and enrollment, Y) in Country A, between 2000-2007 My results ...
-1
votes
0answers
55 views

An efficient algorithm for computing all semigroups of order n [on hold]

I attached two papers which give an algorithm for computing all semigroups of order n=3, and n=5. I understood the first(table 3) and second(table 4) steps of algorithm, but I can't understand the ...
0
votes
2answers
64 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$. ...
8
votes
1answer
281 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 ...
27
votes
9answers
12k views

Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in ...
14
votes
4answers
1k views

Checking if two graphs have the same universal cover

It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere. You can define a notion of "covering graph" in graph theory, ...
4
votes
1answer
286 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
343 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 ...
0
votes
0answers
65 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 ...
7
votes
1answer
89 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 ...
3
votes
0answers
48 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
258 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, ...
0
votes
1answer
100 views

Algorithm to check if a number is the sum of another number and its reverse [closed]

So im looking for an algorithm that checks (in about 10 sec) if a natural number M (1≤M≤10^100000 -yes, the range is that big) can occur by the sum of another natural number N and its reverse Nr. For ...
3
votes
1answer
55 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 ...
1
vote
2answers
45 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
43 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 ...
0
votes
1answer
249 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
5
votes
1answer
172 views

Algorithm for Low Discrepancy Sequence of Hamilton Cycles in Complete Graphs

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand ...
6
votes
3answers
218 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
1answer
86 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 ...
1
vote
2answers
105 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
19
votes
3answers
1k views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
2
votes
0answers
38 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
200 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 ...
8
votes
1answer
634 views

Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support. I am attempting to use the method of bounded ...
0
votes
0answers
31 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$ ...
1
vote
2answers
389 views

Terrain Generation: Infinite 2D space filled with Diffusion-limited aggregation clusters?

Disclaimer: I don't have a deep understanding of fractals or any higher math, I'm just personally interested in it, so please excuse me if I'm using wrong terms or if I'm being inaccurate. Making ...
3
votes
0answers
83 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$. ...
3
votes
2answers
97 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 ...
5
votes
2answers
1k views

Algorithm for solving systems of linear Diophantine inequalities

So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...
4
votes
2answers
194 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 ...
9
votes
4answers
8k views

How to quickly determine whether a given natural number is a power of another natural number?

We have a natural number $n>1$. We want to determine whether there exist natural numbers $a, k>1$ such that $n = a^k$. Please suggest a polynomial-time algorithm.
5
votes
6answers
693 views

Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
3
votes
1answer
205 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 ...
25
votes
1answer
5k views

How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
4
votes
0answers
94 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
58 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
235 views

Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula $$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...
1
vote
0answers
154 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 ...
8
votes
1answer
651 views

Some Questions on the Collatz conjecture

The set of all positive whole numbers is denoted by $\mathbb{N}_+$. Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto \begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ ...
0
votes
0answers
66 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 ...
0
votes
0answers
45 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 ...
2
votes
1answer
597 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
0
votes
1answer
132 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
39 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 ...
10
votes
6answers
1k views

Where on the internet I can find database of graphs?

I am studying graph algorithms. I need database of graphs on which I can test my algorithms. Where can I find reliable database of graphs of all kinds? Thanks!
2
votes
2answers
310 views

Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem. One of the respondents cited Professor David Speyer's Math ...
2
votes
1answer
68 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 ...