Proved
Established implication or scoped theorem in cited mathematics ↗
Chen–Tal–Wang · Depth-two threshold lower bounds · Theorem 1.1, §1.1.1, p. 2 →
Observed Oct 10, 2026
Theorem · version 2
Depth-two threshold circuits require superquadratic size
Statement
For every fixed ε in (0,1), there exists a function f in E^NP not computable by depth-two THR∘THR circuits of size n^{2.5−ε}; the same holds for SYM∘THR.
Assumptions
- ε is fixed; circuit size counts gates under the paper’s convention; arbitrary linear threshold gates.
Scope
The hard function may depend on ε; its class is E^NP, not NP.
Evidence
Source reports
Connections
In this problem · publication v14
P versus NP →
Restricted-model result · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Scope: For each fixed ε > 0, an E^NP function needs depth-two threshold size n^{2.5−ε}; the function may depend on ε.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Chen–Tal–Wang · Depth-two threshold lower bounds →
- Theorem 1.1, §1.1.1, p. 2 → · Original passage ↗
Recorded wording
For every fixed ε in (0,1), there exists a function f in E^NP not computable by depth-two THR∘THR circuits of size n^{2.5−ε}; the same holds for SYM∘THR.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Lijie Chen · Avishay Tal · Yichuan Wang · Preprint · Publication date Mar 15, 2026
Source-reported preprint/project; independent mathematical assessment pending.
Chen–Tal–Wang · Depth-two threshold lower bounds — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: ECCC-TR26-039-observed-2026-10-10. Observed Oct 10, 2026.
AI involvement is not reported by this cited source; this is not a claim of its absence.
Chen–Tal–Wang · Depth-two threshold lower bounds — proof text: ECCC-TR26-039-observed-2026-10-10. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-threshold-2026
- Statement version
- 2
- SHA-256
- f992b8350629c43dcbee8023bd446aa40c52e11e6d370fdf688c59d6b0bdb8a3