Seminar: Unified and Optimal Lower Bounds for Monotone Computation

Robert Robere
Department of Computer Science
University of Toronto

Unified and Optimal Lower Bounds for Monotone Computation

Department of Computer Science
Tuesday, February 7, 2017, 12:00 pm, Room EN 2022


A classic counting argument due to Claude Shannon shows that almost all boolean functions have high complexity --- more formally, all but an exponentially small fraction of boolean functions on n bits require exponential size circuits. On the other hand, the best lower bounds on circuit size that we have proven for any explicit function is on the order of 5n - o(1), which is not even superlinear! The state of affairs is not much better for boolean formulas, for which we merely have cubic lower bounds. Reducing the gap between the trivial lower bound by Shannon and the lower bounds achieved by current technology is a central task of computational complexity theory.

In this talk, we discuss some recent work in which we have matched Shannon's lower bound for computing an explicit function by monotone circuit models. In particular, we prove that a certain monotone variant of the SAT problem requires monotone formulas of size 2 for some universal cn constant c > 0. Our lower bounds are tight (up to the constant c) for any monotone boolean function, and thus represent the first example of any explicit monotone boolean function asymptotically matching the size lower bounds obtained by Shannon in the monotone regime. Moreover, our result is very general and applies to a wide variety of other monotone circuit models.



Department of Computer Science

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000