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 1For 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