{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:19Z","timestamp":1750220179394,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,8,2]],"date-time":"2022-08-02T00:00:00Z","timestamp":1659398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MICIN","award":["IJC2018-035334-I, PID2019-109137GB-C22, PID2019-109137GB-C21"],"award-info":[{"award-number":["IJC2018-035334-I, PID2019-109137GB-C22, PID2019-109137GB-C21"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,8,2]]},"DOI":"10.1145\/3531130.3533344","type":"proceedings-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T20:23:38Z","timestamp":1659644618000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems"],"prefix":"10.1145","author":[{"given":"Ilario","family":"Bonacina","sequence":"first","affiliation":[{"name":"UPC Universitat Politecnica de Catalunya, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria Luisa","family":"Bonet","sequence":"additional","affiliation":[{"name":"UPC Universitat Politecnica de Catalunya, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"volume-title":"Parity and the Pigeonhole Principle","author":"Ajtai M.","key":"e_1_3_2_1_1_1","unstructured":"M. Ajtai . 1990. Parity and the Pigeonhole Principle . Birkh\u00e4user Boston , Boston, MA , 1\u201324. M. Ajtai. 1990. Parity and the Pigeonhole Principle. Birkh\u00e4user Boston, Boston, MA, 1\u201324."},{"key":"e_1_3_2_1_2_1","volume-title":"SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings(Lecture Notes in Computer Science, Vol.\u00a011628)","author":"Atserias Albert","year":"2019","unstructured":"Albert Atserias and Massimo Lauria . 2019 . Circular (Yet Sound) Proofs. In Theory and Applications of Satisfiability Testing - SAT 2019 - 22nd International Conference , SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings(Lecture Notes in Computer Science, Vol.\u00a011628) , Mikol\u00e1s Janota and In\u00eas Lynce (Eds.). Springer, 1\u201318. Albert Atserias and Massimo Lauria. 2019. Circular (Yet Sound) Proofs. In Theory and Applications of Satisfiability Testing - SAT 2019 - 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings(Lecture Notes in Computer Science, Vol.\u00a011628), Mikol\u00e1s Janota and In\u00eas Lynce (Eds.). Springer, 1\u201318."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3265985"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"volume-title":"Proceedings 35th Annual Symposium on Foundations of Computer Science. 794\u2013806","author":"Beame P.","key":"e_1_3_2_1_5_1","unstructured":"P. Beame , R. Impagliazzo , J. Krajicek , T. Pitassi , and P. Pudlak . 1994. Lower bounds on Hilbert\u2019s Nullstellensatz and propositional proofs . In Proceedings 35th Annual Symposium on Foundations of Computer Science. 794\u2013806 . P. Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, and P. Pudlak. 1994. Lower bounds on Hilbert\u2019s Nullstellensatz and propositional proofs. In Proceedings 35th Annual Symposium on Foundations of Computer Science. 794\u2013806."},{"key":"e_1_3_2_1_6_1","volume-title":"An Exponential Separation between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. 80 (10","author":"Beame Paul","year":"1996","unstructured":"Paul Beame and Toniann Pitassi . 1996. An Exponential Separation between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. 80 (10 1996 ), 195\u2013228. Paul Beame and Toniann Pitassi. 1996. An Exponential Separation between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. 80 (10 1996), 195\u2013228."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.05.002"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Maria\u00a0Luisa Bonet Sam Buss Alexey Ignatiev Jo\u00e3o Marques-Silva and Ant\u00f3nio Morgado. 2018. MaxSAT Resolution With the Dual Rail Encoding. In AAAI. 6565\u20136572.  Maria\u00a0Luisa Bonet Sam Buss Alexey Ignatiev Jo\u00e3o Marques-Silva and Ant\u00f3nio Morgado. 2018. MaxSAT Resolution With the Dual Rail Encoding. In AAAI. 6565\u20136572.","DOI":"10.1609\/aaai.v32i1.12204"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103552"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51825-7_13"},{"key":"e_1_3_2_1_11_1","volume-title":"NJ, 1996). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol.\u00a039","author":"Buss R.","year":"1998","unstructured":"Samuel\u00a0 R. Buss . 1998 . Lower bounds on Nullstellensatz proofs via designs. In Proof complexity and feasible arithmetics (Rutgers , NJ, 1996). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol.\u00a039 . Amer. Math. Soc., Providence, RI, 59\u201371. Samuel\u00a0R. Buss. 1998. Lower bounds on Nullstellensatz proofs via designs. In Proof complexity and feasible arithmetics (Rutgers, NJ, 1996). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol.\u00a039. Amer. Math. Soc., Providence, RI, 59\u201371."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-61792-9_27"},{"key":"e_1_3_2_1_14_1","volume-title":"The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0200)","author":"de Rezende F.","year":"2021","unstructured":"Susanna\u00a0 F. de Rezende , Massimo Lauria , Jakob Nordstr\u00f6m , and Dmitry Sokolov . 2021 . The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0200) , Valentine Kabanets (Ed.). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 40:1\u201340:24. Susanna\u00a0F. de Rezende, Massimo Lauria, Jakob Nordstr\u00f6m, and Dmitry Sokolov. 2021. The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021)(Leibniz International Proceedings in Informatics (LIPIcs), Vol.\u00a0200), Valentine Kabanets (Ed.). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 40:1\u201340:24."},{"key":"e_1_3_2_1_15_1","unstructured":"Noah Fleming Stephan Grosser Mika G\u00f6\u00f6s and Robert Robere. 2022. On Semi-Algebraic Proofs and Algorithms. Electron. Colloquium Comput. Complex.(2022) TR22\u2013003.  Noah Fleming Stephan Grosser Mika G\u00f6\u00f6s and Robert Robere. 2022. On Semi-Algebraic Proofs and Algorithms. Electron. Colloquium Comput. Complex.(2022) TR22\u2013003."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Noah Fleming Pravesh Kothari and Toniann Pitassi. 2019. Semialgebraic Proofs and Efficient Algorithm Design. Foundations and Trends\u00ae in Theoretical Computer Science 14 1-2(2019) 1\u2013221.  Noah Fleming Pravesh Kothari and Toniann Pitassi. 2019. Semialgebraic Proofs and Efficient Algorithm Design. Foundations and Trends\u00ae in Theoretical Computer Science 14 1-2(2019) 1\u2013221.","DOI":"10.1561\/0400000086"},{"key":"#cr-split#-e_1_3_2_1_17_1.1","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s Alexandros Hollender Siddhartha Jain Gilbert Maystre William Pires Robert Robere and Ran Tao. 2022. Separations in Proof Complexity and TFNP. CoRR abs\/2205.02168(2022). https:\/\/doi.org\/10.48550\/arXiv.2205.02168 arXiv:2205.02168 10.48550\/arXiv.2205.02168","DOI":"10.1109\/FOCS54457.2022.00111"},{"key":"#cr-split#-e_1_3_2_1_17_1.2","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s Alexandros Hollender Siddhartha Jain Gilbert Maystre William Pires Robert Robere and Ran Tao. 2022. Separations in Proof Complexity and TFNP. CoRR abs\/2205.02168(2022). https:\/\/doi.org\/10.48550\/arXiv.2205.02168 arXiv:2205.02168","DOI":"10.1109\/FOCS54457.2022.00111"},{"key":"e_1_3_2_1_18_1","volume-title":"Bit-complexity in Sums-of-Squares and Polynomial Calculus. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Hakoniemi Tuomas","year":"2021","unstructured":"Tuomas Hakoniemi . 2021 . Monomial size vs . Bit-complexity in Sums-of-Squares and Polynomial Calculus. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021 , Rome, Italy, June 29 - July 2, 2021. IEEE, 1\u20137. Tuomas Hakoniemi. 2021. Monomial size vs. Bit-complexity in Sums-of-Squares and Polynomial Calculus. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. IEEE, 1\u20137."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131313.1131314"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Jan Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press.  Jan Kraj\u00ed\u010dek. 2019. Proof Complexity. Cambridge University Press.","DOI":"10.1017\/9781108242066"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275250"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5516"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51825-7_16"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055478"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188914"},{"key":"e_1_3_2_1_28_1","volume-title":"Exponential Lower Bounds for Monotone Span Programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 406\u2013415","author":"Robere Robert","year":"2016","unstructured":"Robert Robere , Toniann Pitassi , Benjamin Rossman , and Stephen\u00a0 A. Cook . 2016 . Exponential Lower Bounds for Monotone Span Programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 406\u2013415 . Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen\u00a0A. Cook. 2016. Exponential Lower Bounds for Monotone Span Programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 406\u2013415."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1040046140"}],"event":{"name":"LICS '22: 37th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation"],"location":"Haifa Israel","acronym":"LICS '22"},"container-title":["Proceedings of the 37th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533344","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531130.3533344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:09Z","timestamp":1750186929000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531130.3533344"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,2]]},"references-count":31,"alternative-id":["10.1145\/3531130.3533344","10.1145\/3531130"],"URL":"https:\/\/doi.org\/10.1145\/3531130.3533344","relation":{},"subject":[],"published":{"date-parts":[[2022,8,2]]},"assertion":[{"value":"2022-08-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}