Lifting to Parity Decision Trees Via Stifling
summary
Proves a concrete lifting theorem: parity decision tree (PDT) size of S composed with majority on 3 bits is at least 2^{DT(S)}, and more generally if gadget g is k-stifled gadget then PDT size(S∘g) ≥ DT(S)^k. Proof uses an adversary method plus Gaussian elimination on parity constraints to track dependent bits, and composes with gadgets that let the adversary ignore dependencies. Shows examples (majority, indexing) and notes inner product is only 1-stifled, leaving stronger inner-product and DAG simulations open.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:33Decision Trees
- 1:47Proof Complexity
- 4:37Problem with Priority Query Models
- 6:41Composite Relations
- 7:54Lower Bonds
- 8:55Constraints
- 10:04adversary
- 13:35size lifting theorem
related talks
38mLower Bounds on the Space Complexity of Dynamic Programming
34mNew Tools for Peak Memory Scheduling
19mA Formal Disproof of Hirsch Conjecture
26mPrincipled algorithm, data structure and system design for Processing-in-Memory (PIM)”
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
30mDeciding Reachability under Persistent x86-TSO
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems