# Tag Info

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

12

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

11

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.

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

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

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.

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

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