On disperser/lifting properties of the Index and Inner-Product functions
summary
Proves two concrete limits and one positive construction: shows simulation-based lifting methods cannot push gadget size below m < log n − ω(1) by giving counterexamples that break the disperser conjecture for both index and inner‑product gadgets; constructs deterministic lifting from decision trees to parity decision trees using a constant-size index gadget for semi‑structured protocols where Bob only sends parities; translates this to lower bounds in proof complexity by lifting tree‑resolution size to Tree‑Res‑parity size. Techniques: simulation invariants, disperser/extractor analysis, explicit counterexample with blocks of all 0s or 1s.
AI-written summary · about
chapters (10)
- 0:00Introduction to lifting
- 0:23Understanding lifting theorems
- 4:52Block composition and gadgets
- 9:00Overview of results
- 10:20Simulation-based approaches
- 14:30Maintaining invariants
- 17:02Gadget analysis and measures
- 20:42Proving limitations and growth
- 24:24Applications in proof complexity
- 25:33Future directions and conclusion
related talks
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
58mCircuit Complexity and Connections I
10mQuery, Communication and Discrepancy
23mTowards General and Tight Hardness Results for Graph Problems
26mCounting Distinct Elements in the Message Passing Model
29mEquality, Revisited
56mSatisfiability Algorithms II