<p>You can look at the <a href="https://arxiv.org/abs/cs/0606037" rel="noreferrer">survey paper by Bogdanov and Trevisan</a>, and this <a href="https://www.youtube.com/watch?v=Yo-naUur464" rel="noreferrer">survey talk</a> 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:</p>

<ul>
<li>The <a href="https://en.wikipedia.org/wiki/Planted_clique" rel="noreferrer">planted clique problem</a>: 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})$.</li>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.8586&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Feige's random SAT hypothesis</a>: 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})$.</li>
</ul>

CC BY-SA 3.0
2016-11-14T15:49:06.803Z
2016-11-14T15:49:06.803Z
Sasho Nikolov
<p>The <a href="https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science" rel="nofollow noreferrer">list of unsolved problems in computer science</a> 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.</p>

<p>Are there other high-profile, specific open problems in average-case complexity?</p>

CC BY-SA 3.0
2016-11-13T01:31:44.590Z
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
CC BY-SA 3.0
2016-11-13T02:07:05.290Z
There's the planted clique conjecture https://en.wikipedia.org/wiki/Planted_clique#As_a_hardness_assumption
Andrew
<cc.complexity-theory><reference-request><average-case-complexity>
Average-case complexity open problems other than one-way functions
Saram Meti
# Average-case complexity open problems other than one-way functions

(Asked by: username_0 on 2016-11-12)

The [list of unsolved problems in computer science](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, reference-request, average-case-complexity

> **Comments:**
> **username_1**: 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.  
> **username_2**: There's the planted clique conjecture https://en.wikipedia.org/wiki/Planted_clique#As_a_hardness_assumption  

---

## 1 answers

### Answer by username_3 on 2016-11-14. Score: 6

You can look at the [survey paper by Bogdanov and Trevisan](https://arxiv.org/abs/cs/0606037), and this [survey talk](https://www.youtube.com/watch?v=Yo-naUur464) 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](https://en.wikipedia.org/wiki/Planted_clique): 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.8586&rep=rep1&type=pdf): 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})$.


---

