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


Title: Correlation Bounds Against Monotone NC^1
Date: December 22, 2015 (Tuesday)
Time: 2:30 p.m. - 3:30 p.m.
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



Super-polynomial lower bounds against *monotone circuits* have been known since the 1980s. Why haven't these techniques extended to non-monotone boolean circuits? One explanation lies in the "Hamming weight gap": the fact that the YES-instances in these lower bounds (e.g. k-cliques, st-paths) have lower Hamming weight than the NO-instances (e.g. complete (k-1)-partite graphs, st-cuts). This can be seen as a barrier (akin to natural proofs), since lower bound techniques with this property cannot extend to small non-monotone classes like TC^0.

In recent work, we obtain the first super-polynomial lower bound against monotone formulas (a.k.a. the class Monotone NC^1) which is not subject to the Hamming weight gap. Moreover, our result is the first average-case lower bound under the uniform distribution (a.k.a. correlation bound) in the monotone setting. This has some interesting corollaries, including lower bounds against non-monotone NC^1 circuits with (1/2 - o(1))*log(n) negations (which is half the number required to compute any function in NC^1). The proof technique introduces a new notion of "persistent minterms", which might be of independent interest.



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