Luca Trevisan: Average-case Complexity -- A Survey
In this survey talk, we review the many open questions and the few things that are known about the average-case complexity of computational problems.
We will talk about questions such as:
- Can we derive the existence of hard-on-average problems from the existence of hard-in-worst-case problems? What is stopping us from proving statements like "Unless P=NP, there are hard-on-average problems in NP under the uniform distribution" or "Unless P=NP, public-key cryptography is possible"?
- What is going on in Levin's famously concise one-page paper on average-case NP-complete problems?
- For some, but not all, optimization problems, the hardest instances to approximate are random ones. What does this have to do with integrality gaps and inapproximability results?
