## A Tighter Grip on Circuit Depth

Benjamin Rossman, Rocco Servedio, and Li-Yang Tan have made a breakthrough in proving lower bounds on constant-depth circuits. It came from a bi-coastal collaboration of Rossman visiting the Berkeley Simons Institute from Japan and Tan visiting from Berkeley to Servedio at Columbia University in New York. Their new paper solves several 20- and 30-year old open problems.

Today we congratulate them on their achievement and describe part of how their new result works.

What exactly did they prove? As some have already remarked, how one expresses this says something about communications in our field. Exactly what they proved is:

Theorem 1 For some explicit constant \$latex {c > 0}&fg=000000&bg=e8e8e8\$ and all depths \$latex {d geq 2}&fg=000000&bg=e8e8e8\$ up to \$latex {csqrt{log n}/loglog n}&fg=000000&bg=e8e8e8\$, there is an \$latex {n}&fg=000000&bg=e8e8e8\$-ary monotone Boolean function \$latex {f}&fg=000000&bg=e8e8e8\$ that has a simple \$latex {O(n)}&fg=000000&bg=e8e8e8\$-size circuit \$latex {S_d}&fg=000000&bg=e8e8e8\$ (indeed, a formula) of depth \$latex {d}&fg=000000&bg=e8e8e8\$ with unbounded…

View original post 2,076 more words