- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Exponential Lower Bounds for Monotone Computation by...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Exponential Lower Bounds for Monotone Computation by Algebraic Gaps Robere, Robert
Description
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.
Item Metadata
Title |
Exponential Lower Bounds for Monotone Computation by Algebraic Gaps
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2016-09-06T14:04
|
Description |
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.
|
Extent |
60 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: University of Toronto
|
Series | |
Date Available |
2017-03-08
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0343099
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International