Centro Universitário do Pará

Certified Depth–Width Frontiers for Reversible SELECT Circuits: Exact four-target curves, an all-width eight-target lower bound, and DRAT-certified boundary instances

We determine the complete fixed-width depth curve of the four-target one-hot selector SELECT_X in a fully declared classical-reversible model: gate set {X, CNOT, Toffoli}, pairwise-disjoint-support layers, all-to-all connectivity, dirty data targets, and clean ancillae restored t...