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

CREATORMarco Carmosino, Ngu Dang, Tim Jackman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-17942

Browse the full library · About the Tower of Babel