Tag
ac0
- Aug 18, 2025 The Switching Lemma and Why Parity Needs Depth to Compute How random restrictions collapse constant-depth circuits, why the lemma proves AC0 cannot compute parity, and where the argument runs out of room. computation theory
- Feb 2, 2024 The Depth Hierarchy: NC, AC, and the Cost of Wide Gates How NCi and ACi interleave, why the hierarchy collapses if NC1 equals NC, and what the known separations at the bottom actually prove. computation theory