Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere(2018) so that it works for any gadget with high enough rank . We apply our generalizedtheorem to solve two open problems: We present the first result that demonstrates a separation in proof powerfor cutting planes with unbounded versus polynomially bounded coefficients . * We give the first explicit separation between monotonerary formulas andmonotone real formulas . Previously only anon-explicit separation was known . An important technical ingredient, which may be of independent interest, is that we show that the . standard decision treecomplexity and the parity decision tree complexity of the . corresponding decision . tree complexity are equal . In particular, this implies that the standard . decision tree complexity and . the . parity decision Tree complexity of . the correspondingfalsified clause search problem are equal are equal. In addition, we give an explicit family of functionsthat can be computed with monotronary formulas of nearly linear
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20) |
Forlag | IEEE |
Publikationsdato | 1 nov. 2020 |
Sider | 24-30 |
ISBN (Elektronisk) | 978-1-7281-9621-3 |
DOI | |
Status | Udgivet - 1 nov. 2020 |
Begivenhed | 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE - Durham, NC, USA Varighed: 16 nov. 2020 → 19 nov. 2020 |
Konference
Konference | 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE |
---|---|
Land | USA |
By | Durham, NC |
Periode | 16/11/2020 → 19/11/2020 |
ID: 251872578