Questions tagged [algorithms]

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, algorithmic-randomness and algorithmic-topology tags.

Filter by
Sorted by
Tagged with
35 votes
3 answers
7k views

Distinct numbers in multiplication table

Consider the multiplication table for the numbers $1,2,\dots, n$. How many different numbers are there? That is, how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there? I'm ...
falagar's user avatar
  • 2,761
51 votes
4 answers
17k views

How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered. ...
Rune's user avatar
  • 2,386
47 votes
1 answer
3k views

improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...
Jeffrey Shallit's user avatar
44 votes
11 answers
25k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
Xerxes's user avatar
  • 441
7 votes
1 answer
721 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
Mahdi Khosravi's user avatar
21 votes
9 answers
20k views

Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations. Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...
amateur's user avatar
  • 213
65 votes
2 answers
23k views

Does there exist a complete implementation of the Risch algorithm?

Is there a generally available (commercial or not) complete implementation of the Risch algorithm for determining whether an elementary function has an elementary antiderivative? The Wikipedia article ...
Timothy Chow's user avatar
  • 78.1k
44 votes
15 answers
28k views

What are the applications of hypergraphs?

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
29 votes
3 answers
3k views

Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
John Pardon's user avatar
  • 18.3k
24 votes
4 answers
35k views

Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph? All I know is that Alon, Yuster and Zwick use a technique called "color-coding", which has a ...
Hsien-Chih Chang 張顯之's user avatar
16 votes
2 answers
3k views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns $...
Igor Rivin's user avatar
  • 95.6k
11 votes
4 answers
12k views

How to find all integer points on an elliptic curve?

How can I determine the integer points of a given elliptic curve if I know its rank and its torsion group? I read same basic books on elliptic curves but as a non-professional I didn't understand ...
amateur algebraist's user avatar
7 votes
1 answer
437 views

Algorithm for comparing $x + y \cdot \log(z)$ for $x,y,z$ rational?

I'm playing with some methods of comparing two real numbers of the form $x + y \log(z)$, where $x,y,z$ are rational numbers and $z$ is positive. There are various estimates on irrationality measures ...
Marty's user avatar
  • 13.1k
7 votes
1 answer
772 views

Is equality of terms for "real" numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
tailcalled's user avatar
5 votes
3 answers
394 views

Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees

Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$. Assume these degree sequences are graphical: there exist simple graphs (no ...
Matthieu Latapy's user avatar
1 vote
0 answers
176 views

Maximum independent set in dense graphs

Let $0 < A < 1$ and $G$ be connected d-regular graph with degree $d=[A n]$. The density of $G$ is about $A$. Q1 Are there constraints on $A$ such that finding maximum independent set of $G$ is ...
joro's user avatar
  • 24.2k
64 votes
1 answer
4k views

How to be rigorous about combinatorial algorithms?

1. The question This may be the worst question I've ever posed on MathOverflow: broad, open-ended and likely to produce heat. Yet, I think any progress that will be made here will be extremely useful ...
darij grinberg's user avatar
52 votes
2 answers
17k 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}$). ...
Vidit Nanda's user avatar
  • 15.4k
46 votes
7 answers
12k views

What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference? Long version of the question: I'm sort of surprised to be asking this, because ...
Ryan O'Donnell's user avatar
40 votes
5 answers
15k views

Computing the Galois group of a polynomial

Does there exist an algorithm which computes the Galois group of a polynomial $p(x) \in \mathbb{Z}[x]$? Feel free to interpret this question in any reasonable manner. For example, if the degree of $p(...
Simon Thomas's user avatar
  • 8,348
33 votes
3 answers
6k views

Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$, decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective, respectively, injective? -- And ...
Stefan Kohl's user avatar
  • 19.5k
27 votes
1 answer
650 views

Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...
Zakharia Stanley's user avatar
20 votes
2 answers
24k views

Partitioning a polygon into convex parts

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible. I know almost nothing about this subject, so I've been searching on Google ...
user14059's user avatar
  • 201
18 votes
3 answers
3k views

When are (finite) simplicial complexes (smooth) manifolds?

Hi, is there an algorithm that determines if a given simplicial complex is a.) a manifold b.) a smooth manifold c.) homotopy equivalent to a manifold d.) a real algebraic variety ?
Markus Ulke's user avatar
17 votes
9 answers
2k views

Where on the internet I can find a database of graphs?

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

Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$. Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...
David Dumas's user avatar
14 votes
2 answers
730 views

Checking whether given binary operation is a group operation

Given a binary function $f: [1..n] \times [1..n] \to [1..n]$ how to check that this operation is a group operation on $[1..n]$? It's obvious that this can be done in $O(n^3)$ time just by checking ...
falagar's user avatar
  • 2,761
13 votes
3 answers
834 views

Effective algorithm to test positivity

Let $f(x_1,\ldots, x_n)$ be a real polynomial in several variables. Is there an effective algorithm to test whether $f$ is positive (or nonnegative) on the whole of ${\mathbb{R}}^n$?
user avatar
11 votes
3 answers
2k views

Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing $$ M(x)=\sum_{n\le x}\mu(n) $$ takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
Charles's user avatar
  • 8,974
10 votes
1 answer
670 views

Building a polyhedron from areas of its faces

Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for ...
Vladimir Reshetnikov's user avatar
10 votes
2 answers
3k views

Algorithm for embedding a graph with metric constraints

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
Matthew Kahle's user avatar
10 votes
1 answer
561 views

Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction? The answer does ...
Colin McLarty's user avatar
8 votes
1 answer
1k views

Is there an efficient algorithm to check whether two matrices are the same up to row and column permutations?

Define $\mathcal M_n$ as the set of all $n\times n$ matrices with each entry either 1 or $x$. Two such matrices are equivalent iff they can be obtained from each other by swapping pairs of rows and ...
Wolfgang's user avatar
  • 13.2k
8 votes
1 answer
250 views

Algorithmically handling the Spin groups in larg(ish) dimensions

Question: Is there a reasonably efficient algorithmic representation of $\mathit{Spin}_n$? By this I mean, a way to store its elements and operate on them (multiply, inverse, maybe compute ...
Gro-Tsen's user avatar
  • 29.9k
7 votes
4 answers
3k views

Generating Random Curves with Fixed Length and Endpoint Distance

Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given? ...
Manfred Weis's user avatar
  • 12.6k
7 votes
2 answers
624 views

What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath (Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. ...
joro's user avatar
  • 24.2k
6 votes
1 answer
1k views

Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
Bruce Westbury's user avatar
6 votes
2 answers
437 views

Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein (...
Dominic van der Zypen's user avatar
5 votes
1 answer
438 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 ...
Alexey Milovanov's user avatar
5 votes
5 answers
4k views

Package for the Closest Vector Problem (CVP)?

Let $A$ be a positive definite, real $n \times n$ matrix. This defines a norm on $\mathbb{R}^n$. Now I have a given point $p \in \mathbb{R}^n$ and I want to find the lattice point $x \in \mathbb{Z}^n$ ...
Hans's user avatar
  • 2,863
5 votes
2 answers
468 views

Box stacking problem

Real world problem alert: I am moving from my house to another one, and the problem below arised when I tried to fit some little boxes of various shapes into a large box: We are given a positive ...
Dominic van der Zypen's user avatar
5 votes
3 answers
1k views

Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
Miroslav Korbelar's user avatar
3 votes
0 answers
75 views

Random graphs with prescibed degrees and triangles

In short: a random graph model generates (multi-)graphs with prescribed number of edges and minimal number of triangles for each vertex. Questions arise about the actual number of triangles and the ...
Matthieu Latapy's user avatar
3 votes
1 answer
7k views

Detection of Redundant Constraints

Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ...
user avatar
1 vote
5 answers
5k views

The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure. Thanks
pranay's user avatar
  • 201
1 vote
0 answers
106 views

Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances I found so far are non-isomorphic strongly regular graphs with large automorphism groups. Q1 What are hard instances for the ...
joro's user avatar
  • 24.2k
0 votes
1 answer
179 views

Bound on queries to a tree with unusual probabilties -- follow-up

This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...
Michael Jarret's user avatar
37 votes
10 answers
18k 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 $...
ilyaraz's user avatar
  • 1,771
36 votes
2 answers
3k views

Does anyone want a pretty Maass form?

A few months ago, I was curious about some properties of Maass cusp forms, of nonabelian arithmetic origin. As a result, I went through a somewhat predictable process of finding a totally real $A_4$ ...
34 votes
3 answers
3k views

Quickly determining if a matrix has any PSD completion

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion? Slightly more precisely: for simplicity let's assume ...
Paul Christiano's user avatar