Lifting to Parity Decision Trees via Stifling (with applications to proof complexity)

on YouTube ↗01h 05m

" summary

Proves a lifting theorem that turns any deterministic decision tree lower bound for a relation R into a parity decision tree size lower bound for R composed with a small gadget g as long as g is a stifling gadget. Shows constant-size gadgets work, e.g. Indexing on 3 bits, Inner Product on 4 bits and Majority on 3, and random functions. Gives the simulation: PDT size ≥ 2^k · DT(R) when g is k‑stifled, and uses this to convert tree‑like resolution width lower bounds into Res‑Lin size lower bounds.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:05Proof complexity
3. 4:40CNFs
4. 14:43State of 867
5. 19:43Weak points
6. 22:10Stifling
7. 28:30Example
8. 29:34Stifling Functions
9. 31:05Indexing Function
10. 33:07Proof
11. 40:32New Priority Queries
12. 43:10Parity Decision Tree
13. 50:00Inner Product

" related talks

• 54mConstraints, Gadgets, and InvariantsAndrei Bulatov · Counting Complexity and Phase Transitions Boot Camp
• 01h 17mInapproximability of Constraint Satisfaction Problems VJohan Håstad · Real Analysis Boot Camp 2013
• 01h 22mTutorial 5: The GCT Chasm IIKetan Mulmuley · Geometric Complexity Theory 2014
• 01h 17mInapproximability of Constraint Satisfaction Problems IIIJohan Håstad · Real Analysis Boot Camp 2013
• 55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order LogicBenjamin Rossman · Symmetry, Logic, Computation 2016
• 23mA New Connection Between Node and Edge Depth Robust GraphsJeremiah Blocki, Mike Cinkoske · ITCS 2021
• 01h 09mInformation Theory in Computational Complexity IVJaikumar Radhakrishnan · Information Theory Boot Camp 2015
• 33mLucky Talk: Exponential Separation of Information and CommunicationGillat Kol · Information Theory in Complexity Theory and Combinatorics 2015