A Finite Alternation Result for Reversible Boolean Circuits
summary
For n ≥ 4 every even reversible Boolean function on n bits decomposes as a composition of at most nine reversible maps that each act on n−1 bits, with a proved lower bound of five and a constructive combinatorial proof based on viewing the domain as 2×A×2 and manipulating column patterns. The proof yields a bounded alternation depth nine normal‑form strategy, a recursive synthesis algorithm with worst‑case size O(9^n), and a playable web app that implements the constructive moves; the decomposition requires the overall permutation to be even.
AI-written summary · about
chapters (8)
- 0:00Start
- 1:20Reversible Boolean Circuits
- 4:57Permutation Groups
- 7:08Linear Circuits
- 7:51Permutations
- 16:56Outline of the Proof
- 25:01Write a Single Three Cycle as a Product of Two Balanced Permutations
- 26:39The Algorithm for Solving a Rubik's Cube
related talks
01h 01mTop-Down Lower Bounds for Depth-Four Circuits
51mOn constant T-depth circuits
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
22mSymmetries in Reversible Programming: From Symmetric Rig Groupoids to Reversible
39mStructure of the Fourier Spectrum of Boolean Functions and Complexity
30mSymbolic Execution of Hadamard-Toffoli Quantum Circuits
20mPolynomial-time Classical Simulation of Roetteler’s Shifted Bent Function Algo...