Section 6.3, paragraph 2In the restricted regime gates collapse to AC0; AC0 approximates counting but has tiny parity correlation
External cited result A published result used as background or input; not proved in Lean here.
1 Paper text
Our focus is a restricted literal-threshold regime: fixed total depth, nonnegative weights on Boolean literals, and thresholds bounded in units of the smallest nonzero weight. In this regime, each gate has a constant-size witness and collapses to a constant-width DNF, yielding an abstraction (Theorem 2.4). Constant-depth circuits can implement approximate counting (Ajtai, 1993), yet they have exponentially small correlation with parity (Furst et al., 1984; Håstad, 1986; Smolensky, 1987; Razborov, 1987). Learning parity depends on the architecture and training setting; both difficulties and positive results have been studied (Thornton, 1996b,a; Daniely and Malach, 2020). The representational lower bound here applies only to the explicit gate model. Section 6.4 gives a complementary Fourier/spectral interpretation of this local-versus-global parity separation.
Generated from paper_jmlr.tex, lines 927–931.
2 Explain this
The paper's answer: it studies a restricted regime (fixed total depth, nonnegative weights on Boolean literals, thresholds bounded in units of the smallest weight). There each gate has a constant-size witness and collapses to a constant-width DNF, so the whole model is in AC0 (Theorem 2.4).
AC0 can still do a lot: it can approximately count (Ajtai). But AC0 functions have exponentially small correlation with parity (Furst–Saxe–Sipser, Håstad, Smolensky, Razborov). Whether parity is learnable depends on the architecture and training setting; the literature has both negative and positive results.
3 How this is formalised
The collapse is Theorem 2.4 (checked). Approximate counting, the correlation bounds and the learning
literature are cited classical results; the correlation bound enters Lean only as the named input HastadNegl
(Remark 2.3 (global parity)).
| Paper anchor | sec:majority-vs-parity-p2 (website anchor; the manuscript has no label here) |
|---|---|
| Displayed as | Section 6.3, paragraph 2 |
| Claim | In the restricted regime gates collapse to AC0; AC0 approximates counting but has tiny parity correlation |
| Coverage category | External cited result |
| Statement source | paper_jmlr.tex lines 927–931; SHA-256 of the normalised block source eceec6bc4e5101e2… |
| Depends on | Theorem 2.4 |
| Explanations | explain/c-majority-regime, formal/c-majority-regime |
| Build evidence | fresh isolated rebuild, audit report |
4 Lean statement and source
No Lean statement corresponds to this claim. This is a published classical result. It is cited, not proved in this Lean development.
Build evidence: fresh isolated rebuild of all 38 bundled modules with Lean (version 4.26.0, started 2026-10-10T15:21:56Z, finished 2026-10-10T15:27:00Z: 38/38 modules compiled, 1588 axiom reports, no errors. See Build for the commands and the independent audit of 2026-10-10 (dated evidence).