Gate elimination arguments for Boolean circuit lower bounds can be made constructive, producing efficient refuters that output counterexamples for undersized circuits.
Problems Parameterized by Treewidth Tractable in Single Exponential Time:
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
years
2026 2verdicts
UNVERDICTED 2representative citing papers
Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.
citing papers explorer
-
Constructive Separations from Gate Elimination
Gate elimination arguments for Boolean circuit lower bounds can be made constructive, producing efficient refuters that output counterexamples for undersized circuits.
-
Fine-Grained Bounds for Courcelle's Theorem
Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.