Skip to main content

Robert Robere: Unified and optimal lower bounds for monotone computation

Time: Mon 2017-05-29 12.00

Location: Room 4523, Lindstedtsvägen 5, KTH CSC

Participating: Robert Robere, University of Toronto

Export to calendar

PRACTICALITIES: Lunch is served at 12:00 noon (please register with your full name at this doodle  at the latest by the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.

ABSTRACT

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 strongly exponential (i.e. \(2^{Ω(n)}\)) 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. Even for monotone circuits and formulas, which are much more understood, the best lower bounds for explicit functions are weakly exponential (i.e. of the form \(2^{n^c}\) where c < 1).

In this talk, we discuss some recent work in which we have nearly matched Shannon's lower bound for computing an explicit function by monotone circuit models. In particular, we prove that a monotone variant of the SAT problem requires monotone formulas of size \(2^{c*n}\) for some universal 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 with strongly exponential size lower bounds. Furthermore, our techniques are very general and apply to a wide variety of monotone circuits models.

This work is joint with Toniann Pitassi.