Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt

Standard

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. / de Rezende, Susanna F.; Meir, Or; Nordström, Jakob; Pitassi, Toniann; Robere, Robert; Vinyals, Marc.

Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, 2020. s. 24-30.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt

Harvard

de Rezende, SF, Meir, O, Nordström, J, Pitassi, T, Robere, R & Vinyals, M 2020, Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. i Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, s. 24-30, 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE
, Durham, NC, USA, 16/11/2020. https://doi.org/10.1109/FOCS46700.2020.00011

APA

de Rezende, S. F., Meir, O., Nordström, J., Pitassi, T., Robere, R., & Vinyals, M. (2020). Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. I Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20) (s. 24-30). IEEE. https://doi.org/10.1109/FOCS46700.2020.00011

Vancouver

de Rezende SF, Meir O, Nordström J, Pitassi T, Robere R, Vinyals M. Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. I Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE. 2020. s. 24-30 https://doi.org/10.1109/FOCS46700.2020.00011

Author

de Rezende, Susanna F. ; Meir, Or ; Nordström, Jakob ; Pitassi, Toniann ; Robere, Robert ; Vinyals, Marc. / Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, 2020. s. 24-30

Bibtex

@inproceedings{6db14a2772534e629e1349d9becc3ba0,
title = "Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity",
abstract = "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",
author = "{de Rezende}, {Susanna F.} and Or Meir and Jakob Nordstr{\"o}m and Toniann Pitassi and Robert Robere and Marc Vinyals",
note = "To appear; 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE<br/> ; Conference date: 16-11-2020 Through 19-11-2020",
year = "2020",
month = nov,
day = "1",
doi = "10.1109/FOCS46700.2020.00011",
language = "English",
pages = "24--30",
booktitle = "Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)",
publisher = "IEEE",

}

RIS

TY - GEN

T1 - Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

AU - de Rezende, Susanna F.

AU - Meir, Or

AU - Nordström, Jakob

AU - Pitassi, Toniann

AU - Robere, Robert

AU - Vinyals, Marc

N1 - To appear

PY - 2020/11/1

Y1 - 2020/11/1

N2 - 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

AB - 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

U2 - 10.1109/FOCS46700.2020.00011

DO - 10.1109/FOCS46700.2020.00011

M3 - Article in proceedings

SP - 24

EP - 30

BT - Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)

PB - IEEE

T2 - 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE<br/>

Y2 - 16 November 2020 through 19 November 2020

ER -

ID: 251872578