UPDATED: Room Change [Thesis Defense - Rahul Ilango] Metacomplexity and Metacryptography

Abstract:

In this thesis, we show --- for the first time --- how to achieve two longstanding dream results in theoretical computer science, under common assumptions. First, we determine the exact computational complexity of finding optimal circuits. Specifically, we show that the Minimum Circuit Size Problem is NP-complete, a dream result since Levin defined NP-completeness in 1973. Second, we construct traditional mathematical proofs that reveal nothing other than the truth of the statement being proven. Specifically, we show that zero-knowledge proofs for NP with perfect soundness and truly no interaction are effectively possible, a dream result since Goldwasser, Micali, and Rackoff defined zero-knowledge in 1985. A core part of both results is a "meta'' perspective on the areas of complexity theory and cryptography.