Skip to main navigation
Skip to Content
Computer Science
University of Toronto
Quercus
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Mar 28
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Mar 28
Event date: Friday, March 28, 2014, at 2:10 PM
Location: GB244 *UPDATED Time & Location
Speaker: Benjamin Rossman, National Institute of Informatics, Tokyo
Title: Formulas vs. Circuits for Small Distance Connectivity
Abstract:
In this talk, I will present a recent result which gives the first super-polynomial separation in the power of bounded-depth (unbounded fan-in) boolean formulas vs. circuits. Consider the elementary fact that every depth-d circuit of size S is equivalent to a depth-d formula of size at most S^d. We prove that a blow-up of S^Ω(d) is necessary for all d <= logloglog S; previously no lower bound better than S^Ω(1) was known for any super-constant d. This result follows from a novel formula size lower bound for the problem of Distance-k st-Connectivity. As a further corollary, we obtain a tight Ω(log k) lower bound on the depth of polynomial-size circuits solving Distance-k st Connectivity for all k <= loglog n. This improves the previous Ω(loglog k) lower bound of Beame, Impagliazzo, Pitassi (1998) and matches the O(log k) upper bound from Savitch's algorithm.