Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.23958 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910168411799552 |
|---|---|
| author | Carmosino, Marco Dang, Ngu Jackman, Tim |
| author_facet | Carmosino, Marco Dang, Ngu Jackman, Tim |
| contents | Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2022). Every circuit lower bound is implicitly existential: every circuit that is too small to compute $f$ must err on some input. This raises a natural question: are these lower bounds \emph{constructive}? That is, can we efficiently produce such errors? Chen, Jin, Santhanam, and Williams showed that constructivity plays a central role in many longstanding open problems in complexity theory, and explicitly raised the question of which circuit lower bound techniques can be made constructive (FOCS 2021).
We show that a variety of gate elimination arguments yield refuters -- efficient algorithms that, when given a circuit that is too small to compute a function $f$, produce an input on which the circuit errs. Our results range from elementary lower bounds for $XOR$ and the multiplexer to more sophisticated arguments for affine dispersers. Underlying these results is a shift in perspective: gate elimination arguments \emph{are} algorithms. Each step either simplifies the circuit or reveals a violation of some structural or functional property, from which, with a little additional work, explicit counterexamples can be extracted.
We further strengthen the $XOR$ result to handle circuits that \emph{match} the lower bound: given any DeMorgan circuit of size $3(n-1)$ that fails to compute $XOR_n$, we can efficiently produce a counterexample. While refuters follow from the gate elimination arguments themselves, this refinement requires a complete characterization of the set of optimal circuits computing $XOR$ -- a requirement rarely met by other explicit functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23958 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Constructive Separations from Gate Elimination Carmosino, Marco Dang, Ngu Jackman, Tim Computational Complexity Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art $3.1n - o(n)$ bound for affine dispersers (STOC 2022). Every circuit lower bound is implicitly existential: every circuit that is too small to compute $f$ must err on some input. This raises a natural question: are these lower bounds \emph{constructive}? That is, can we efficiently produce such errors? Chen, Jin, Santhanam, and Williams showed that constructivity plays a central role in many longstanding open problems in complexity theory, and explicitly raised the question of which circuit lower bound techniques can be made constructive (FOCS 2021). We show that a variety of gate elimination arguments yield refuters -- efficient algorithms that, when given a circuit that is too small to compute a function $f$, produce an input on which the circuit errs. Our results range from elementary lower bounds for $XOR$ and the multiplexer to more sophisticated arguments for affine dispersers. Underlying these results is a shift in perspective: gate elimination arguments \emph{are} algorithms. Each step either simplifies the circuit or reveals a violation of some structural or functional property, from which, with a little additional work, explicit counterexamples can be extracted. We further strengthen the $XOR$ result to handle circuits that \emph{match} the lower bound: given any DeMorgan circuit of size $3(n-1)$ that fails to compute $XOR_n$, we can efficiently produce a counterexample. While refuters follow from the gate elimination arguments themselves, this refinement requires a complete characterization of the set of optimal circuits computing $XOR$ -- a requirement rarely met by other explicit functions. |
| title | Constructive Separations from Gate Elimination |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2604.23958 |