Convergent Gate Elimination and Constructive Circuit Lower Bounds
Marco Carmosino, Ngu Dang, Tim Jackman · 2026
Read Convergent Gate Elimination and Constructive Circuit Lower Bounds by Marco Carmosino, Ngu Dang, Tim Jackman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-17942.txt.
Description
Marco Carmosino and team advance gate elimination, the only known method for complexity lower bounds for explicit functions against Boolean circuits. They formalize circuit simplification as a convergent term graph rewriting system, and give a constructive proof of a classical lower bound with it.
First, circuit simplification is a convergent system over DeMorgan and AND-OR-XOR bases, with local rules from Boolean identities, so every trimming sequence ends in an identical result. Convergence lets researchers reason about trimmed circuits regardless of order. No similar convergent formalization exists over the U2 and B2 bases. Then they use the system for a constructive bound stretching Schnorr's result that XOR needs three times n minus one gates in the DeMorgan basis. A constructive bound supplies a refuter algorithm that efficiently finds counter-cases for every circuit for the function. Until this work, no constructive bound had been proved via gate elimination.
Catalog record
| CREATOR | Marco Carmosino, Ngu Dang, Tim Jackman |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-17942