The Chinese University of Hong Kong
Department of Computer Science and Engineering


Title: Lower Bounds for Bounded-Depth Formulas
Date: December 22, 2015 (Tuesday)
Time: 11:00 a.m. - 12:00 noon
Venue: Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong,
Shatin, N.T.
Speaker: Dr. Benjamin Rossman
Assistant Professor
National Institute of Informatics, Japan



A classic result of Hastad (1986) shows that depth d+1 Boolean circuits computing the PARITY function require exp(n^{1/d}) gates. In recent work, we prove a stronger (moreover tight) exp(dn^{1/d}) lower bound for Boolean *formulas*. The proof technique studies a random process where Hastad's Switching Lemma is applied to formulas in a more efficient manner.



Prof. Benjamin Rossman got his PhD from MIT, under the supervision of Madhu Sudan. He is an assistant professor at National Institute of Informatics, Tokyo, and will be joining University of Toronto in the summer of 2016. Prof. Rossman has made important contributions to complexity theory and logic, especially the areas of circuit complexity and finite model theory. His dissertation won George M. Sprowls Award (for best doctoral theses in Computer Science and MIT) and Ackermann Award (by the European Association for Computer Science and Logic). His recent works also won best paper awards at FOCS 2015, CCC 2014, and CSR 2014.


Enquiries: Miss Evelyn Lee at tel 3943 8444

For more information, please refer to