# Tagged Questions

The algorithms tag has no wiki summary.

**44**

votes

**4**answers

2k views

### What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...

**36**

votes

**1**answer

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

**35**

votes

**4**answers

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

**31**

votes

**7**answers

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

**30**

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

**29**

votes

**1**answer

3k views

### An edge partitioning problem on cubic graphs

Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...

**28**

votes

**3**answers

2k views

### Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy.
Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...

**28**

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

**26**

votes

**4**answers

2k views

### Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples:
1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...

**26**

votes

**1**answer

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

**25**

votes

**3**answers

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

**25**

votes

**2**answers

929 views

### Groebner basis with group action

At one point my advisor, Mark Haiman, mentioned that it would be nice if there was a way to compute Groebner bases that takes into account a group action.
Does anyone know of any work done along ...

**23**

votes

**19**answers

3k views

### What is the easiest randomized algorithm to motivate to the layperson?

When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**23**

votes

**4**answers

2k views

### Can Gröbner bases be used to compute solutions to large, real-world problems?

In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several ...

**21**

votes

**8**answers

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

**20**

votes

**12**answers

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

**20**

votes

**3**answers

1k views

### Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...

**20**

votes

**0**answers

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

**19**

votes

**0**answers

536 views

+250

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...

**18**

votes

**1**answer

3k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...

**18**

votes

**3**answers

3k views

### Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...

**17**

votes

**2**answers

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

**17**

votes

**10**answers

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

**17**

votes

**0**answers

163 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**16**

votes

**5**answers

3k views

### Fastest Algorithm to Compute the Sum of Primes?

Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...

**16**

votes

**8**answers

2k views

### Determine if circle is covered by some set of other circles

Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius ...

**16**

votes

**6**answers

4k views

### Algorithms for finding rational points on an elliptic curve?

I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, ...

**16**

votes

**5**answers

2k views

### duplicate detection problem

Restated from stackoverflow:
Given:
array a[1:N] consisting of integer elements in the range 1:N
Is there a way to detect whether the array is a permutation (no duplicates) or whether it has any ...

**16**

votes

**3**answers

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

**3**answers

847 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**16**

votes

**2**answers

2k views

### Inverting the totient function

For what values of $n$ does the equation $\phi(x) = n$ have at least one solution? Is there any efficient way to check it for a given $n$?
It obviously has no solutions for odd $n$. And the smallest ...

**15**

votes

**12**answers

2k views

### Lower Bounds in Theoretical Computer Science

Besides the classical: you can't do comparison sort with faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must ...

**15**

votes

**9**answers

2k views

### How can I generate random permutations of [n] with k cycles, where k is much larger than log n?

I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...

**15**

votes

**4**answers

788 views

### Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:
Show, for all integers $1 \leq i \leq k$, that the univariate ...

**15**

votes

**4**answers

2k views

### FFTs over finite fields?

I'm trying to understand how to compute a fast Fourier transform over a finite field. This question arose in the analysis of some BCH codes.
Consider the finite field $F$ with $2^n$ elements. It is ...

**15**

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

**15**

votes

**1**answer

2k views

### Conceptual explanation of Strassen's trick for matrix multiplication

Algorithms for fast multiplication of polynomials and integers have well-known conceptual explanations. A good survey paper is Daniel J. Bernstein's Fast Multidigit Multiplication for Mathematicians.
...

**14**

votes

**5**answers

566 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**14**

votes

**5**answers

1k views

### Algorithm generalizing continued fractions for non-quadratic algebraic numbers

The continued fraction algorithm generates an integer sequence which terminates for a rational number, is periodic for the roots of irreducible integer quadratics, and is non-periodic for other ...

**14**

votes

**1**answer

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

**14**

votes

**2**answers

301 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...

**13**

votes

**4**answers

2k views

### How Does One Find the “Loneliest Person on the Planet”?

I'm looking for the algorithm that efficiently locates the "Loneliest Person on the Planet", where "loneliest" is defined as:
Maximum minimum distance to another person -- that is, the person for ...

**13**

votes

**3**answers

6k 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 Noga Alon et al. use the techinique called "color-coding",
which has a running ...

**13**

votes

**3**answers

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

**13**

votes

**2**answers

652 views

### Are the axioms for higher category-theory effectively computable?

I ask this, although I don't conduct any research in the area, or even plan to. -- There seems to be general agreement that the axioms for higher categories grow very rapidly in complexity as the ...

**13**

votes

**6**answers

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

**13**

votes

**3**answers

2k views

### Computing the maximum salary

To motivate my question, I will describe a related problem and then give a solution to it. My question will then be a variant of this problem.
N individuals sit around a table and want to compute the ...

**13**

votes

**2**answers

887 views

### What is the most compelling reason to believe Church's thesis? [closed]

Church's thesis states that the Turing machine is a universal model of computation. What is the most compelling argument supporting this assertion?

**13**

votes

**2**answers

918 views

### Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given ...