Six-bit parity needs six hidden threshold gates in a layered depth-two threshold circuit
A strictly layered depth-two threshold circuit has hidden linear threshold gates that read only the inputs and one threshold output gate that reads only the hidden gates. Such a circuit computes PARITY_n with n hidden gates, and it has long been asserted, without proof, that n hidden units are necessary (first for sigmoid units, where it is false, and later for threshold units). To our knowledge the only proofs for threshold units cover n ≤ 4 (Fung and Li, 2001) and, as a corollary of the hypercube-slicing bound, n ≤ 5. For n = 6 the slicing bound is 5 and leaves the question open. We prove that 6 hidden gates are necessary for PARITY_6; 6 is the first n at which the minimum exceeds the slicing bound, which answers a question of Arslanov, Amirgalieva and Kenshimov (2016). The proof is a symmetry reduction followed by a SAT instance whose clauses are valid for every threshold function; its unsatisfiability is certified by DRAT proofs checked with drat-trim, and an unrelated CP-SAT model over bounded integer weights gives the same answer. The output gate matters: five threshold hidden gates suffice if the output may be an arbitrary Boolean function.
Authors
- Xintian Huang (ORCID: https://orcid.org/0009-0000-7664-7108)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24354679
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint