A Tighter Grip on Circuit Depth

Gödel's Lost Letter and P=NP


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

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s