Section 6.3, paragraph 1Scale-adaptive threshold models (TC0) can represent parity
External cited result A published result used as background or input; not proved in Lean here.
1 Paper text
One might object that modern networks can implement majority-like decisions, suggesting (threshold circuits) as the “right” complexity class. Indeed, if one allows scale-adaptive thresholds/biases or fan-in dependent re-scaling, constant-depth threshold models can represent parity-type computations.
Generated from paper_jmlr.tex, lines 924–925.
2 Explain this
A natural objection: real networks compute majority-like functions, so maybe (threshold circuits) is the right model, not AC0. Indeed, with scale-adaptive thresholds or fan-in-dependent rescaling, constant-depth threshold models can compute parity.
3 How this is formalised
A classical fact about threshold circuits, cited. The paper's model deliberately excludes such thresholds; the checked boundary example is Remark 2.2 (model scope).
| Paper anchor | sec:majority-vs-parity-p1 (website anchor; the manuscript has no label here) |
|---|---|
| Displayed as | Section 6.3, paragraph 1 |
| Claim | Scale-adaptive threshold models (TC0) can represent parity |
| Coverage category | External cited result |
| Statement source | paper_jmlr.tex lines 924–925; SHA-256 of the normalised block source 05a789dd205282b0… |
| Explanations | explain/c-majority-objection, formal/c-majority-objection |
| 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).