Rafael Pass (Cornell University)

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.