Every Optimal Circuit for Parity Partitions into a Binary Tree

Every optimal circuit for Parity over the DeMorgan basis can be decomposed into a binary tree of two-bit parity sub-circuits. This characterization of the set of optimal circuits for Parity makes it a candidate for proving that MCSP is hard via Reverse Gate Elimination --- the technique used by Ilango to show that MCSP for partial functions is hard under ETH. We obtain the characterization by extracting structural information from Schnorr's gate-elimination proof of 3(n-1) lower bounds for Parity.

Joint work with Timothy Jackman & Nathan Dang.