{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:45:11Z","timestamp":1787503511383,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384288","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"78-90","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["(Semi)Algebraic proofs over {\u00b11} variables"],"prefix":"10.1145","author":[{"given":"Dmitry","family":"Sokolov","sequence":"first","affiliation":[{"name":"St. Petersburg State University, Russia \/ Steklov Institute of Mathematics at St. Petersburg, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302964"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389944"},{"key":"e_1_3_2_1_3_1","first-page":"18","article-title":"Lower Bounds for Polynomial Calculus: Non-Binomial Case","volume":"242","author":"Alekhnovich Michael","year":"2003","unstructured":"Michael Alekhnovich and Alexander A. Razborov . 2003 . Lower Bounds for Polynomial Calculus: Non-Binomial Case . Proceedings of the Steklov Institute of Mathematics , 242 (2003), 18 \u2013 35 . Available at http:\/\/people.cs.uchicago.edu\/ razborov\/files\/misha.pdf Michael Alekhnovich and Alexander A. Razborov. 2003. Lower Bounds for Polynomial Calculus: Non-Binomial Case. Proceedings of the Steklov Institute of Mathematics, 242 (2003), 18\u201335. Available at http:\/\/people.cs.uchicago.edu\/ razborov\/files\/misha.pdf","journal-title":"Proceedings of the Steklov Institute of Mathematics"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.24"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365714"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2018.11"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1726"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294258"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243126"},{"key":"e_1_3_2_1_13_1","volume-title":"Optimal Sherali-Adams Gaps from Pairwise Independence","author":"Georgiou Konstantinos","unstructured":"Konstantinos Georgiou , Avner Magen , and Madhur Tulsiani . 2009. Optimal Sherali-Adams Gaps from Pairwise Independence . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Irit Dinur, Klaus Jansen, Joseph Naor, and Jos\u00e9 Rolim (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 125\u2013139. isbn:978-3-642-03685-9 Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. 2009. Optimal Sherali-Adams Gaps from Pairwise Independence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Irit Dinur, Klaus Jansen, Joseph Naor, and Jos\u00e9 Rolim (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 125\u2013139. isbn:978-3-642-03685-9"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743515"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00446-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.17323\/1609-4514-2002-2-4-647-679"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00055-0"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230742"},{"key":"e_1_3_2_1_20_1","first-page":"24","article-title":"The Surprising Power of Constant Depth Algebraic Proofs","volume":"26","author":"Impagliazzo Russell","year":"2019","unstructured":"Russell Impagliazzo , Sasank Mouli , and Toniann Pitassi . 2019 . The Surprising Power of Constant Depth Algebraic Proofs . Electronic Colloquium on Computational Complexity (ECCC) , 26 (2019), 24 . https:\/\/eccc.weizmann.ac.il\/report\/2019\/024 Russell Impagliazzo, Sasank Mouli, and Toniann Pitassi. 2019. The Surprising Power of Constant Depth Algebraic Proofs. Electronic Colloquium on Computational Complexity (ECCC), 26 (2019), 24. https:\/\/eccc.weizmann.ac.il\/report\/2019\/024","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102722"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029951"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2015.467"},{"key":"e_1_3_2_1_25_1","volume-title":"Resolution with Counting: Lower Bounds over Different Moduli. CoRR, abs\/1806.09383","author":"Part Fedor","year":"2018","unstructured":"Fedor Part and Iddo Tzameret . 2018. Resolution with Counting: Lower Bounds over Different Moduli. CoRR, abs\/1806.09383 ( 2018 ), arxiv:1806.09383. arxiv:1806.09383 Fedor Part and Iddo Tzameret. 2018. Resolution with Counting: Lower Bounds over Different Moduli. CoRR, abs\/1806.09383 (2018), arxiv:1806.09383. arxiv:1806.09383"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/031\/07"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the International Congress of Mathemeticians. III, 451\u2013460","author":"Pitassi Toniann","year":"1998","unstructured":"Toniann Pitassi . 1998 . Unsolvable Systems of Equations and Proof Complexity . In Proceedings of the International Congress of Mathemeticians. III, 451\u2013460 . Toniann Pitassi. 1998. Unsolvable Systems of Equations and Proof Complexity. In Proceedings of the International Congress of Mathemeticians. III, 451\u2013460."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.04.001"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Alexander Razborov. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes 333\u2013338.  Alexander Razborov. 1987. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes 333\u2013338.","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Dmitry Sokolov. 2020. (Semi)Algebraic Proofs over {\u00b1 1} Variables. https:\/\/eccc.weizmann.ac.il\/report\/2020\/012\/  Dmitry Sokolov. 2020. (Semi)Algebraic Proofs over {\u00b1 1} Variables. https:\/\/eccc.weizmann.ac.il\/report\/2020\/012\/","DOI":"10.1145\/3357713.3384288"},{"key":"e_1_3_2_1_32_1","volume-title":"Now Publishers Inc","author":"Vadhan Salil P.","year":"1985","unstructured":"Salil P. Vadhan . 2012. Pseudorandomness. Now Publishers Inc ., Hanover, MA, USA . isbn:160 1985 940, 9781601985941 Salil P. Vadhan. 2012. Pseudorandomness. Now Publishers Inc., Hanover, MA, USA. isbn:1601985940, 9781601985941"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384288","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384288","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384288"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":32,"alternative-id":["10.1145\/3357713.3384288","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384288","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}