Tag
circuit-depth
- Aug 20, 2025 Circuit Families and the Non-Uniform Model of Computation How a Boolean circuit encodes one fixed input length, why decision problems need whole families of them, and what the missing uniformity assumption costs. 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