Tag
lower-bounds
- 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
- Feb 2, 2026 The Comparison Sorting Lower Bound and What It Actually Counts Why comparison sorts need about n log n comparisons, how the decision-tree and adversary arguments differ, and which cost models the bound leaves out. algorithms
- Jan 26, 2026 Razborov-Smolensky and the Limits of Modulo Gates How low-degree polynomials over a finite field stand in for constant-depth circuits, and why AC0 with MOD-p gates cannot compute MOD-q for a different prime. computation theory
- Jan 17, 2026 Comparison Lower Bounds From Decision Trees and Adversaries Counting distinguishable outcomes gives the n log n sorting bound. When that counting is not available, an adversary argument supplies the same conclusion by a different route. algorithms
- Nov 6, 2025 Monotone Circuits and the Approximation Method Why negations make lower bounds hard, how Razborov and Alon-Boppana proved exponential monotone size for clique, and what the method cannot say about matching. computation theory
- Nov 2, 2025 The Natural Proofs Barrier and Why Circuit Lower Bounds Stall What makes a lower-bound argument natural, why such arguments cannot separate P from NP unless factoring is easy, and which techniques escape the barrier. 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
- 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
- Jun 3, 2024 The Inverse Ackermann Bound and Why It Is Effectively Constant How the α(n) function is defined, why the amortized cost of a disjoint-set sequence lands there, and what the matching lower bound says about improving it. data structures