**21**

votes

**2**answers

3k views

### Distinct numbers in multiplication table

Consider multiplication table for numbers $1,2,\cdots, 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 interested ...

**23**

votes

**10**answers

11k 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 ...

**5**

votes

**1**answer

507 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 ...

**16**

votes

**2**answers

1k 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 ...

**41**

votes

**4**answers

11k 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.
...

**27**

votes

**1**answer

468 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 ...

**14**

votes

**3**answers

2k 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
?

**12**

votes

**2**answers

460 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 ...

**9**

votes

**1**answer

383 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 ...

**6**

votes

**1**answer

890 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}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an ...

**3**

votes

**3**answers

3k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**4**

votes

**1**answer

290 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 ...

**7**

votes

**2**answers

454 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 ...

**6**

votes

**2**answers

315 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 ...

**27**

votes

**5**answers

7k 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 ...

**27**

votes

**9**answers

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 ...

**31**

votes

**2**answers

2k 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$ ...

**37**

votes

**1**answer

2k 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 ...

**19**

votes

**4**answers

2k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**16**

votes

**1**answer

3k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**11**

votes

**4**answers

2k views

### Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ?
(Main case - complex numbers, comments on other cases are also welcome. "Given" ...

**21**

votes

**0**answers

415 views

### Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them.
Define the set $\mathcal{E}$ of ...

**17**

votes

**4**answers

2k views

### Complexity of testing integer square-freeness

How fast can an algorithm tell if an integer is square-free?
I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH ...

**10**

votes

**6**answers

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!

**9**

votes

**2**answers

477 views

### When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?

To ask this question in a (hopefully) more direct way:
Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ ...

**13**

votes

**2**answers

1k views

### Detecting almost-primes quickly

There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product ...

**12**

votes

**8**answers

6k 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 ...

**6**

votes

**2**answers

625 views

### Differential ideal membership problem

We know that in the ordinary algebra ideal case, the ideal membership problem can be solved by the Grobner Base theory, then, is there a counterpart theory in the differential ideal case?
To be ...

**19**

votes

**3**answers

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 ...

**14**

votes

**6**answers

6k views

### Good algorithm for finding the diameter of a (sparse) graph?

My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here:
I have a large, connected, sparse graph in ...

**12**

votes

**1**answer

540 views

### Stable matchings when switches have costs

The Gale-Shapley algorithm finds a stable matching in the complete bipartite graph, for any preference matrix. It's also well-known that stable matchings don't always exist in the complete graph ...

**6**

votes

**1**answer

435 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 ...

**5**

votes

**1**answer

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 ...

**4**

votes

**2**answers

254 views

### What's the current state of one-rule semi-Thue system termination problem?

What's the current state of one-rule semi-Thue system termination problem? Search produces a lot of references, but it's hard to find out if decidability of this problem has been proven or not.

**4**

votes

**2**answers

1k views

### How to compute the rook polynomial of a Ferrers board?

Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...

**3**

votes

**0**answers

281 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...

**29**

votes

**3**answers

2k 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 ...

**16**

votes

**2**answers

4k views

### Generalization of the shakehands/condom puzzle?

The classic handshake puzzle goes something like this:
"Given that everyone has a different skin disease, how can you safely shake hands with 3 people when you have only 2 gloves?"
Its common ...

**10**

votes

**1**answer

292 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**10**

votes

**3**answers

473 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$?

**7**

votes

**1**answer

1k views

### How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...

**7**

votes

**4**answers

2k views

### Stirling Number of first kind : Implementation

Hi everybody,
Does there exist an explicit formula for the Stirling Numbers of the First Kind which are given by the formula
$$
x(x-1)\cdots (x-n+1) = \sum_{k=0}^n s(n,k)x^k.
$$
Otherwise, what is ...

**6**

votes

**2**answers

2k views

### Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...

**4**

votes

**0**answers

195 views

### Comparing different Euclidean algorithms on a Euclidean domain

I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...

**1**

vote

**2**answers

157 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**9**

votes

**3**answers

1k 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. ...

**7**

votes

**1**answer

417 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 ...

**6**

votes

**2**answers

324 views

### Wants: Polynomial Time Algorithm for Decomposing a Multiset of Rationals into Two Additive Subsets.

First, allow me to say that this problem was posed to me by a professor in the department. It is related to his research in a way that I do not know. However, since I couldn't come up with anything ...

**5**

votes

**0**answers

181 views

### Differential operators that preserve real-rootedness

Is there some description of polynomial differential operators, $\mathcal{D}=\sum f_i(x) D_x^i$ such that, if $h$ is a polynomial all of whose roots are in $[0,1]$, then so are all the roots of ...

**2**

votes

**1**answer

104 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 ...