Natural Proofs in Algebraic Circuit Complexity
summary
Shows two concrete results: bounded-coefficient polynomials in VP-prime admit nontrivial algebraic equations computable by small circuits, constructed by diagonalizing over explicit hitting sets via Chinese-remainder-style encoding; and under an exponential hardness assumption for permanent, the standard hardness-to-randomness generator produces VNP-like coefficient vectors that form hitting sets for VP, so any VP-equation would yield an explicit VP vs VNP separation. Techniques: universal circuits, hardness→pseudorandomness, and nonuniform encoding; constructions succeed under stated hypotheses.
AI-written summary · about
chapters (11)
- 0:00Start
- 5:23Algebraic Circuits
- 7:30Algebraic circuit complexity: Basics
- 10:11Equations for Polynomials: Recap
- 13:00Using equations to prove lower bounds
- 14:35Algebraic Natural Proofs
- 19:46Two (types of) Questions
- 31:14Equations for VP: Ideas
- 35:23Equations for VP': Comments
- 38:43No* VP-equations for VNP: Ideas
- 43:35Open Directions
related talks
01h 17mInapproximability of Constraint Satisfaction Problems V
49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
01h 00mAverage-case Complexity for Polynomials, and All That
53mNew Lower Bounds and Derandomization for ACC, and a...
01h 01mThe Gospel According to TCS
01h 25mInapproximability of Constraint Satisfaction Problems IV
01h 22mTutorial 5: The GCT Chasm II