Thursday, May 20, 2021 - 4:30pm to 5:30pm
Location:
Virtual Presentation - ET Remote Access - ZoomSpeaker:
MUTHURAMAKRISHNAN VENKITASUBRAMANIAM , Associate Professor https://www.cs.rochester.edu/people/faculty/venkitasubramaniam_muthu/index.htmlAverage-case Complexity Through the Lens of Interactive Puzzles
Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes.
Both one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems---namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words, ”It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true.”
This result follows from a more general study of interactive puzzles—a generalization of average-case hardness in NP—and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols.
More about the Speaker.
Joint work with Rafael Pass.
Zoom Participation. See announcement.