5

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?

Saram Meti
  • 111
  • 4
  • 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 01:31
  • There's the planted clique conjecture https://en.wikipedia.org/wiki/Planted_clique#As_a_hardness_assumption – Andrew Nov 13 '16 at 02:07

1 Answers1

6

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})$.
Sasho Nikolov
  • 18,189
  • 2
  • 67
  • 115