A Short List of Equalities Has Large Sign Rank
summary
Constructs a concrete depth‑two threshold-of-threshold function — essentially odd-max-bit of equality — and proves it has unexpectedly large sign rank (about 2^{n^{1/4}} sign rank), separating it from weight‑restricted depth‑two (majority-of-majority) circuits. Proof uses spectral/sign‑rank techniques inspired by Forster’s spectral method and UPP/unbounded‑error communication complexity. Consequences: bottom‑weight restrictions do matter, the function sits in P^MA yet resists sign‑rank lower bounds that sufficed for previous separations.
AI-written summary · about
chapters (23)
- 0:00Intro
- 0:16Linear Threshold Gates
- 1:08Limitations of Linear Threshold Question: What can't it represent?
- 2:19Depth-2 Networks
- 4:38Weights in Halfspaces
- 6:26Communication Complexity of IP
- 7:15Consequences for Depth-2 Circuits
- 8:57Known Limitations of Depth-2
- 10:08The Weight Hierarchy
- 11:04Unbounded Communication Game
- 13:03Sign-Rank And UPP
- 14:17Sign-Rank: Geometric View
- 16:05Sign-Rank of Some Functions
- 17:15Forster's Breakthrough
- 18:34Updated Weight Hierarchy
- 20:21Past Work on Sign Rank
- 20:39A Natural Candidate in Depth-2
- 21:26Towards a Structured Target
- 23:30Our Main Result
- 24:26Structural Communication Complexity Longstanding Open Problem (BFS'86) Prove some F (possibly IP) is not in PH
- 25:07Communication Complexity Landscape
- 26:58Refined Landscape
- 27:52Future: Cross Sign-Rank Barrier Main Problem: Limitations of THRO THR circuits ?