A Survey of Recent Results on Depth Reduction and Lower Bounds for Arithmetic Circuits
summary
Presents an explicit family — the iterated matrix multiplication polynomials (trace of product of D matrices, matrices of size about D^{10}) — and proves any decomposition as a sum of products of homogeneous factors (each forced to be low degree ≈ √D by the argument) requires size at least about 2^{Ω(√D log D)} (roughly 2^{Ω(√D)}). Proof converts high-order singularities into a rank of an exponential matrix and lower-bounds that rank using a form of Alon’s almost‑orthogonality inequality plus Hilbert-style dimension arguments and random‑restriction mod ideals; the construction and bound succeed.
AI-written summary · about