[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*REMINDER*

THEORY SEMINAR
 
Tuesday, October 22, 2013
3:00 p.m.
Ryerson 251
 
Benjamin Rossman
Post doc @Tokyo Inst. of Tech.
brossman at theory.csail.mit.edu
 
Title:  “Formulas vs. Circuits for Small Distance Connectivity”
 
Abstract: One of the major open questions in complexity theory is whether poly-size boolean circuits are more powerful than poly-size boolean formulas (that is, whether NC^1 is different from P).  The *monotone* version of this separation was proved over 20 years ago by Karchmer and Widgerson.  In this talk, we present results giving the first separation of formulas vs. circuits in the *bounded depth* setting.  This separation comes via a novel lower bound for STCONN(k(n)), the problem of determining whether a graph of size n contains a path of length <= k(n) between two distinguished vertices.  We show that solving STCONN(k(n)) on unbounded fan-in boolean FORMULAS of depth <= log(n)/polyloglog(n) requires size n^Omega(log k) for all k(n) <= loglog(n) (in contrast, this problem has poly-size CIRCUITS of depth only O(log k)).  In addition to separating the power of formulas vs. circuits up to depth logloglog(n), this implies a tight lower bound of Omega(log k) on the depth of poly-size circuits for STCONN(k(n)), improving a previous Omega(loglog k) lower bound of Beame, Impagliazzo and Pitassi [FOCS 1995].
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131022/e0b65d38/attachment.htm