Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

18

This type of problem has been the subject of quite a bit of study. You can find references by googling random self-reducibility, and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.

15

The Wikipedia entry that Peter linked to mentions a few important examples of problems that have worst-case to average case reductions, like the permanent. Shortest vector problem (as well as related lattice problems) is another important example, see Ajtai's paper and what came after it (works by Regev, Micciancio, Peikert,...). One of the only general ...

14

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ...

11

It might be conjectured that the Learning Parity with Noise Problem (LPN) at constant error rate requires time $2^{n^{1-o(1)}}$. The fastest known algorithm (Blum-Kalai-Wasserman) uses time $2^{O(n/\log n)}$.

10

(1): This question was studied in the paper "Towards proving strong direct product theorems" by Ronen Shaltiel, and it turns out that such a conjecture is false: For example, it could be that $f$ can be computed with probability $0.99 * p$ with size much smaller than $s$, and only the additional $0.01 * p$ probability mass requires size $s$. In such case, ...

10

It's not quite the same as "every algorithm", but in SODA'04 Achlioptas Beame and Molloy suggested that every backtracking algorithm should require exponential time on random 3SAT instances with $n$ variables and $cn$ clauses, with $c$ chosen within a range of values near the satisfiability threshold.

7

Just to complement Or's reply, questions of the flavor of (1) [how much of a resource is needed to do well on k copies] were studied, and the corresponding theorems are called "direct sum theorems". As with direct product theorems, direct sum theorems may or may not hold, depending on the setup.

6

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the worst-case running time is $L_n(1/3, 2.77)$ unconditionally and $L_n(1/3, (64/9)^{1/3})$ under GRH. This is not for the "classic" number field sieve, but a ...

5

There are several psuedorandom number generators that we have no polynomial time algorithms for breaking. I guess you could consider them to be hard on average cases. Check out the generators at www.ecrypt.eu.org/stream/ There are others of course, you can research most of them online.

5

(This is a more detailed version of my comment on the question.) As for your question 1, your class is R, the class of decidable problems. Expected polynomial time is not a useful resource restriction when you allow unbounded error. To prove that your class contains R, consider a language L∈R. Let M be a Turing machine for L which halts on every input. ...

5

You can look at the survey paper by Bogdanov and Trevisan, and this survey talk by Luca. The main open question is whether $\mathsf{P} \neq \mathsf{NP}$ implies that there exist hard on average problems in $\mathsf{NP}$. There are also more concrete conjectures about specific problems, two of which were mentioned in the comments: The planted clique problem: ...

4

The assumptions often used in crypto are a form of average-case complexity assumptions, such as hardness of factoring or discrete log in various groups. Many lattice problems used for strong hardness guarantees for lattice based cryptography are qualitatively somewhat different than the factoring/discrete log based cryptographic assumptions. The ...

3

The bounded post correspondence problem is complete for RNP (Randomized NP). Therefore, it is believed to be hard on average over uniformly random distributions of inputs. Y. Gurevich, Average case completeness, J. Comp. Sys. Sci., 42 (3): 346–398, 1991

2

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") runtime of a version of the Simplex algorithm by a polynomial, though the degree of the polynomial is not stated there.

2

If Graph Isomorphism is randomly self-reducible in the sense of the question (clarified in the comments), then it could be solved in poly time. The reason is that there is in fact an average-case linear time algorithm for GI (even a canonical form) [BK]. For Group Isomorphism, this is not known. However, it's also somewhat of a funny question, because of ...

Only top voted, non community-wiki answers of a minimum length are eligible