[Colloquium] 11/6 Research at TTIC: Li-Yang Tan, TTIC

[Mary Marre]

*When: *    Friday, November 6th at noon

*Where:*    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who: *       Li-Yang Tan, TTIC

*Title:*   An Average-Case Depth Hierarchy Theorem for Boolean Circuits

*Abstract: *
We prove an average-case depth hierarchy theorem for Boolean circuits over
the standard basis of AND, OR, and NOT gates.  Our hierarchy theorem says
that for every $d \geq 2$, there is an explicit $n$-variable Boolean
function $f$, computed by a linear-size depth-$d$ formula, which is such
that any depth-$(d-1)$ circuit that agrees with $f$ on $(1/2 + o_n(1))$
fraction of all inputs must have size $\exp(n^{\Omega(1/d)}).$  This
answers an open question posed by Håstad in his Ph.D. thesis.

Our average-case depth hierarchy theorem implies that the polynomial
hierarchy is infinite relative to a random oracle with probability 1,
confirming a conjecture of Håstad, Cai, and Babai.  We also use our result
to show that there is no "approximate converse" to the results of Linial,
Mansour, Nisan and Boppana on the total influence of constant-depth
circuits, thus answering a question posed by O'Donnell, Kalai, and Hatami.

A key ingredient in our proof is a notion of random projections which
generalize random restrictions.

Joint work with Ben Rossman and Rocco Servedio.

***************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20151031/895bfd3b/attachment.htm