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

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?

• First, I wouldn't call the existence of owf a problem about average complexity. If you are looking for similar questions check the list of open problems in crypto. – Kaveh Nov 13 '16 at 1:31
• There's the planted clique conjecture en.wikipedia.org/wiki/Planted_clique#As_a_hardness_assumption – Andrew Nov 13 '16 at 2:07

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