Tag
parity
- 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
- Jun 5, 2024 Size-Depth Tradeoffs and the Block-Respecting Model How restricting a circuit to communicate only between fixed blocks of inputs turns depth into a measurable resource, and what the resulting bounds say about parity. computation theory