Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic
summary
States that colored Subgraph Isomorphism has nearly tight AC0 circuit lower bounds — circuits need n^{Ω(treewidth / log treewidth)} — and AC0 formulas require superpolynomial size, proved as n^{Ω(tree-depth^c)} for some c>0. Proofs use tailored average-case hard distributions (colored random graphs X_β built from Markov-chain threshold weightings), minor-monotonicity and a polynomial grid/tree-minor theorem to reduce to three obstruction families. Consequences translate these to FO: variable-width lower bounds and a polynomial quantifier-rank bound for the finite homomorphism preservation theorem.
AI-written summary · about
chapters (19)
- 0:00Intro
- 1:07Outline
- 4:16Reductions
- 6:21Boolean Circuits
- 8:42Boolean Formulas
- 10:26AC Circuit and Formulas
- 15:32Implications
- 16:20Upper Bounds
- 17:15Tree-width: tw(G)
- 18:38Tree-depth: td(G)
- 20:41Lower Bounds
- 25:57Average-Case for SUB(G)
- 30:11G-colored random graph X
- 31:31Proof Sketch
- 33:23Recall
- 34:39Minor-Monotonicity
- 43:02Classical Preservation Theorems
- 45:34Survival on Finite Structures
- 51:39Summary (Last Slide!)
related talks
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
01h 09mInformation Theory in Computational Complexity IV
18mOn the Verification of a Subgraph Construction Algorithm
01h 03mDecay of Correlations in Spin Systems
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
48mUnprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
53mNew Lower Bounds and Derandomization for ACC, and a...
33mConnections Between QBF Proof Complexity and Circuit Complexity