- Simple reductions to circuit minimization
- Project Year:
2021
- REU Student (s):
Vishal Ramesh | Charles University (Prague, Czech Republic)
| Noah Singer | Harvard University MA
- Student 1 Institution:
Harvard University
- Student 2 Institution:
Charles University (Prague, Czech Republic)
- Project Mentor:
Eric Allender
- Project Mentor Area:
Computer Science
- Project Abstract:
The complexity of the minimum circuit size problem (MCSP) - and its many variants, including the minimum Kolgomorov time-complexity problem (MKTP) - is linked intricately to countless other questions in theoretical computer science. For instance, NP-hardness of MCSP or MKTP is known to imply ZPP ≠ EXP, and even if such reductions exist, they cannot be nearly as simple as the standard NP-completeness reductions for other problems. In this project, we study whether various variants of circuit minimization can be complete for NP, or smaller classes, under simple types of reductions. Specifically, we investigate the following questions. Can recent hardness results for MKTP be extended to MCSP? How important is adaptivity in NP-hardness reductions for circuit minimization? How robust is the recent definition of non-interactive statistical zero-knowledge with logspace-bounded verifiers and simulators?
