Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • Susanna F. de Rezende
  • Or Meir
  • Nordström, Jakob
  • Toniann Pitassi
  • Robert Robere
  • Marc Vinyals
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
OriginalsprogEngelsk
TitelProceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)
ForlagIEEE
Publikationsdato1 nov. 2020
Sider24-30
ISBN (Elektronisk)978-1-7281-9621-3
DOI
StatusUdgivet - 1 nov. 2020
Begivenhed61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
- Durham, NC, USA
Varighed: 16 nov. 202019 nov. 2020

Konference

Konference61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
LandUSA
ByDurham, NC
Periode16/11/202019/11/2020

ID: 251872578