@inproceedings{10.1145/3531130.3533344,
    Abstract = {We characterize the strength of the algebraic proof systems Sherali-Adams () and Nullstellensatz () in terms of Frege-style proof systems. Unlike bounded-depth Frege, has polynomial-size proofs of the pigeonhole principle (). A natural question is whether adding to bounded-depth Frege is enough to simulate . We show that , with unary integer coefficients, lies strictly between tree-like and tree-like Resolution. We introduce a weighted version of () and we show that with integer coefficients lies strictly between tree-like and Resolution. Analogous results are shown for using the bijective (i.e. onto and functional) pigeonhole principle and a weighted version of it.},
    Address = {New York, NY, USA},
    Author = {Bonacina, Ilario and Bonet, Maria Luisa},
    BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science},
    File = {On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems - 3531130.3533344.pdf},
    ISBN = {9781450393515},
    Keywords = {Sherali-Adams, Pigeonhole Principle, bounded-depth Frege, Nullstellensatz},
    Location = {Haifa, Israel},
    Publisher = {Association for Computing Machinery},
    Series = {LICS '22},
    Title = {On the Strength of Sherali-Adams and Nullstellensatz as Propositional Proof Systems},
    URL = {https://doi.org/10.1145/3531130.3533344},
    Year = {2022},
    articleno = {25},
    bdsk-url-1 = {https://doi.org/10.1145/3531130.3533344},
    date-added = {2022-08-29 14:27:27 +0200},
    date-modified = {2022-08-29 14:27:27 +0200},
    numpages = {12},
    doi = {10.1145/3531130.3533344}
}

@inproceedings{10.1145/3531130.3533344, Abstract = {We characterize the strength of the algebraic proof systems Sherali-Adams () and Nullstellensatz () in terms of Frege-style proof systems. Unlike bounded-depth Frege, has polynomial-size proofs of the pigeonhole principle (). A natural question is whether adding to bounded-depth Frege is enough to simulate . We show that , with unary integer coefficients, lies strictly between tree-like and tree-like Resolution. We introduce a weighted version of () and we show that with integer coefficients lies strictly between tree-like and Resolution. Analogous results are shown for using the bijective (i.e. onto and functional) pigeonhole principle and a weighted version of it.}, Address = {New York, NY, USA}, Author = {Bonacina, Ilario and Bonet, Maria Luisa}, BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science}, File = {On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems - 3531130.3533344.pdf}, ISBN = {9781450393515}, Keywords = {Sherali-Adams, Pigeonhole Principle, bounded-depth Frege, Nullstellensatz}, Location = {Haifa, Israel}, Publisher = {Association for Computing Machinery}, Series = {LICS '22}, Title = {On the Strength of Sherali-Adams and Nullstellensatz as Propositional Proof Systems}, URL = {https://doi.org/10.1145/3531130.3533344}, Year = {2022}, articleno = {25}, bdsk-url-1 = {https://doi.org/10.1145/3531130.3533344}, date-added = {2022-08-29 14:27:27 +0200}, date-modified = {2022-08-29 14:27:27 +0200}, numpages = {12}, doi = {10.1145/3531130.3533344} }