All reports by Author Muthuramakrishnan Venkitasubramaniam:

__
TR20-051
| 15th April 2020
__

Rafael Pass, Muthuramakrishnan Venkitasubramaniam#### Is it Easier to Prove Theorems that are Guaranteed to be True?

Rafael Pass, Muthuramakrishnan Venkitasubramaniam

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 ... more >>>