Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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?

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

ISSN 1433-8092 | Imprint