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
, Durham, NC, USA, 16/11/2020. https://doi.org/10.1109/FOCS46700.2020.00011
APA
Vancouver
Author
Bibtex
}
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