Addition is Exponentially Harder than Counting for Shallow Monotone Circuits

on YouTube ↗15m

" summary

Defines U_d_n as d n‑bit numbers whose sum is at least 2^n, a monotone function represented by a single threshold gate. Proves any depth-d monotone majority circuit computing U_d_n needs size about 2^{n^{1/d}}, and gives a matching upper bound by a divide‑and‑conquer construction. Uses inductively constructed hard distributions over 0/1 inputs and crucially exploits monotonicity and weight bounds. Consequence: a 3‑layer AC0 implementation with negations achieves exponential speedup over bounded‑depth monotone circuits.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:28Weighted threshold functions
3. 0:57Threshold circuits: Definition Each internal gate computes a weighted threshold function.
4. 1:25Threshold circuits: The frontier Simple computational model whose power remains mysterious
5. 2:02Threshold Circuits vs. Majority Circuits
6. 2:31Polynomial weight is sufficient
7. 3:29Goldmann and Karpinski, 1993
8. 4:01Previous Work Hofmeister, 1992
9. 5:49The lower bound
10. 8:22Monotone Complexity
11. 9:18The Ajtai-Gurevich Theorem (1987) Motivated by question in Finite Model Theory.
12. 10:49Our second result.
13. 12:09Concluding Remarks Addition function Un monotone bounded-depth circuits are