Open Collections

Exponential Lower Bounds for Monotone Computation by Algebraic Gaps

Banff International Research Station for Mathematical Innovation and Discovery

In 1990, following up on the (now renowned) work of Karchmer and Wigderson connecting communication complexity and formula size, Razborov introduced a simple rank-based complexity measure and used it to give a nice proof of quasipolynomial monotone formula lower bounds for a monotone function in NP. It turns out that the rank measure can be used to lower bound both undirected switching network size and span program size. Despite this, essentially the only known lower bounds against the rank measure follow from Razborov's original result. In this talk, we will discuss our recent results providing the first exponential lower bounds on the rank measure for functions in monotone P. This has a number of corollaries in monotone complexity theory, including: the first exponential lower bounds for monotone span programs (indeed, the first superpolynomial lower bounds for monotone span programs computing a function in monotone P); a new and arguably simpler proof of the beautiful lower bounds by Potechin and Chan/Potechin against monotone switching networks; and the first lower bounds against monotone comparator circuits. Our lower bound is obtained by relating the rank measure to a new algebraic complexity measure on search problems that we call the algebraic gap complexity, which may be of independent interest. This work is joint with Steven Cook, Toniann Pitassi, and Ben Rossman.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: University of Toronto

2017-03-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60823

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/