Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

  • 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
Original languageEnglish
Title of host publicationProceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)
PublisherIEEE
Publication date1 Nov 2020
Pages24-30
ISBN (Electronic)978-1-7281-9621-3
DOIs
Publication statusPublished - 1 Nov 2020
Event61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
- Durham, NC, United States
Duration: 16 Nov 202019 Nov 2020

Conference

Conference61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
LandUnited States
ByDurham, NC
Periode16/11/202019/11/2020

Bibliographical note

To appear

ID: 251872578