Tag
circuit-size
- Feb 25, 2026 The Counting Argument for Circuit Size Lower Bounds Why almost every Boolean function on n bits needs about 2^n/n gates, how Lupanov matched that bound from above, and why the argument cannot name a single hard function. computation theory
- 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
- Mar 2, 2025 Gate Basis, Fan-In, and What Circuit Size Actually Counts Why the de Morgan basis, NAND alone, and unbounded fan-in bases give different gate counts, and how the conversions between them are constructed. computation theory
- Jan 17, 2025 Formula Size and the Tree-Shaped Restriction on Circuits What is lost when every gate may feed only one consumer, why parity needs a quadratic formula, and how circuit size converts to formula size at a quadratic cost. computation theory