Luca Trevisan: Average-case Complexity -- A Survey

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?