Richard M. Karp Distinguished Lecture — Average-Case Complexity through the Lens of Interactive Arguments

Consider the following two fundamental open problems in complexity theory:

• Does a hard-on-average language in NP imply the existence of one-way functions?
• Does a hard-on-average language in NP imply a hard problem in TFNP (i.e., the class of total NP search problems)?

We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where NP is hard-on-average, but one-way functions do not exist), TFNP is hard (on average).

This result follows from a more general theory of interactive average-case complexity, and in particular, a novel round-collapse theorem for computationally-sound interactive arguments, analogous to Babai-Moran's celebrated round-collapse theorem for interactive proofs.

Joint work with Muthuramakrishnan Venkitasubramaniam. No prior knowledge of average-case complexity, interactive arguments, TFNP or one-way functions will be assumed.