Average-case complexity open problems other than one-way functions

Question

The list of unsolved problems in computer science on Wikipedia lists no problems in average-case complexity, except "Do one-way functions exist?" which is whether there is a polynomial time computable function that such that all efficient algorithms fail (with high probability) to invert it.

Are there other high-profile, specific open problems in average-case complexity?

Answer 1

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: distinguish between a uniformly random graph on $n$ vertices, and a uniformly random graph in which we have planted a $k$-clique on a random $k$-subset of the vertices. Conjectured to be hard for $k = \omega(\log n)$, $k = o(\sqrt{n})$.
• Feige's random SAT hypothesis: for every $\Delta$, any polynomial time algorithm which never refutes a satisfiable 3SAT formula will fail to refute most 3SAT formulas with $\Delta n$ clauses. It is consistent with current knowledge that this hypothesis may hold even up to $\Delta = o(\sqrt{n})$.