The Easy Witness Lemma
summary
Shows that a weakening of Natural Proofs — a quasi‑natural property (constructive, nonempty but only occasionally large) — is essentially equivalent to circuit lower bounds for nondeterministic exponential time, i.e. to NE ⊄ P/poly. Uses the standard hardness-to-pseudorandom-generator reduction, replaces randomness by nondeterminism to get time bounds like 2^{t^{o(1)}}, and builds succinct witnesses (circuits encoding exponential witnesses) to derive the equivalence.
AI-written summary · about
chapters (10)
- 0:00Inverse circuit analysis
- 1:59Defining natural properties
- 6:05Cryptographic implications
- 10:28Derandomization connections
- 19:03Variants of natural properties
- 24:09Hierarchy and complexity
- 28:25Non-constructive existence
- 34:00Quasi-natural properties
- 44:24Barely natural properties
- 52:13Open problems and conclusion
related talks
29mEquality, Revisited
29mAmplifying Contextual Distance in Higher-Order Languages, using the Law of Large Numbers
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
23mTowards General and Tight Hardness Results for Graph Problems
16mParameterized Verification of Disjunctive Timed Networks
31mParameterized Verification of Systems with Precise (0,1)-Counter Abstraction
35mWhy Extension-Based Proofs Fail
35mSuperlinear Lower Bounds for Multipass Graph Processing