{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T11:09:21Z","timestamp":1655291361272},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","funder":[{"name":"Russian Science Foundation","award":["Project 16-11-10123"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384245","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"source":"Crossref","is-referenced-by-count":3,"title":["Semi-algebraic proofs, IPS lower bounds, and the \u03c4-conjecture: can a natural number be negative?"],"prefix":"10.1145","author":[{"given":"Yaroslav","family":"Alekseev","sequence":"first","affiliation":[{"name":"Steklov Institute of Mathematics at St. Petersburg, Russia \/ St. Petersburg State University, Russia"}]},{"given":"Dima","family":"Grigoriev","sequence":"additional","affiliation":[{"name":"CNRS, France \/ University of Lille, France"}]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[{"name":"Steklov Institute of Mathematics at St. Petersburg, Russia"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5558-9911","authenticated-orcid":false,"given":"Iddo","family":"Tzameret","sequence":"additional","affiliation":[{"name":"Royal Holloway University of London, UK"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"IPS Lower Bounds and the-Conjecture: Can a Natural Number be Negative? ArXiV: http:\/\/arxiv.org\/abs\/","author":"Alekseev Yaroslav","year":"1911"},{"key":"e_1_3_2_1_2_1","first-page":"24","volume-title":"34th Computational Complexity Conference, CCC 2019","author":"Atserias Albert","year":"2019"},{"key":"e_1_3_2_1_3_1","first-page":"307","volume-title":"STOC","author":"Barak Boaz","year":"2012"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_3_2_1_5_1","first-page":"11","volume-title":"35th Symposium on Theoretical Aspects of Computer Science, STACS 2018","author":"Berkholz Christoph","year":"2018"},{"key":"e_1_3_2_1_6_1","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry. MPS-SIAM Series on Optimization","author":"Blekherman Grigoriy","year":"2013"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/265020"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_9_1","volume-title":"On defining integers and proving arithmetic circuit lower bounds. Computational Complexity, 18 ( 1 ): 81-103","author":"B\u00fcrgisser Peter","year":"2009"},{"key":"e_1_3_2_1_10_1","volume-title":"Polynomial size proofs of the propositional pigeonhole principle. The Journal of Symbolic Logic, ( 52 ): 916-927","author":"Buss Samuel R.","year":"1987"},{"key":"e_1_3_2_1_11_1","volume-title":"Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Computational Complexity, 6 ( 3 ): 256-298","author":"Buss Samuel R.","year":"1996"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.06.020"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237860"},{"key":"e_1_3_2_1_14_1","first-page":"135","volume-title":"1974","author":"Stephen","year":"1974"},{"key":"e_1_3_2_1_15_1","volume-title":"The relative eficiency of propositional proof systems. J. Symb. Log., 44 ( 1 ): 36-50","author":"Cook Stephen A.","year":"1979"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03173-5"},{"key":"e_1_3_2_1_17_1","volume-title":"Semialgebraic proofs and eficient algorithm design. Electronic Colloquium on Computational Complexity (ECCC), 26 : 106","author":"Fleming Noah","year":"2019"},{"key":"e_1_3_2_1_18_1","first-page":"32","volume-title":"31st Conference on Computational Complexity, CCC 2016","author":"Forbes Michael A.","year":"2016"},{"key":"e_1_3_2_1_19_1","volume-title":"4th Workshop, CSL ' 90, Heidelberg, Germany, October 1-5, 1990, Proceedings","volume":"533","author":"Goerdt Andreas","year":"1990"},{"key":"e_1_3_2_1_20_1","volume-title":"10th Innovations in Theoretical Computer Science Conference, ITCS 2019","author":"G\u00f6\u00f6s Mika","year":"2019"},{"key":"e_1_3_2_1_21_1","first-page":"1778","volume":"47","author":"G\u00f6\u00f6s Mika","year":"2018","journal-title":"J. Comput."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8192-0"},{"key":"e_1_3_2_1_23_1","volume-title":"Complexity of semialgebraic proofs. Mosc. Math. J., 2 ( 4 ): 647-679, 805","author":"Grigoriev Dima","year":"2002"},{"key":"e_1_3_2_1_24_1","first-page":"1","volume":"113","author":"Grigoriev Dima","year":"2002","journal-title":"Ann. Pure Appl. Logic"},{"key":"e_1_3_2_1_25_1","volume-title":"Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65 ( 6 ): 37 : 1-37 : 59","author":"Joshua","year":"2018"},{"key":"e_1_3_2_1_26_1","volume-title":"Hilbert's invariant theory papers. Lie Groups: History, Frontiers and Applications","author":"Hilbert David","year":"1978"},{"key":"e_1_3_2_1_27_1","series-title":"Dagstuhl Seminar 18051","first-page":"124","volume-title":"Proof Complexity","author":"Hirsch Edward","year":"2018"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214000"},{"key":"e_1_3_2_1_29_1","volume-title":"The surprising power of constant depth algebraic proofs. Electronic Colloquium on Computational Complexity (ECCC), 26 : 24","author":"Impagliazzo Russell","year":"2019"},{"key":"e_1_3_2_1_30_1","volume-title":"Lower bounds for the polynomial calculus and the gr\u00f6bner basis algorithm. Computational Complexity, 8 ( 2 ): 127-144","author":"Impagliazzo Russell","year":"1999"},{"key":"e_1_3_2_1_31_1","volume-title":"Lower bounds of static lovasz-schrijver calculus proofs for tseitin tautologies. Zapiski Nauchnyh Seminarov POMI, 340 : 10-32","author":"Itsykson Dmitry","year":"2006"},{"key":"e_1_3_2_1_32_1","volume-title":"Anneaux preordonnes. Journal d'Analyse Math\u00e9matique, 12 ( 1 ): 307-326","author":"Krivine J. L.","year":"1964"},{"key":"e_1_3_2_1_33_1","series-title":"SIAM Journal on Computing","first-page":"1424","volume-title":"Characterizing propositional proofs as noncommutative formulas","author":"Li Fu","year":"2018"},{"key":"e_1_3_2_1_34_1","volume-title":"Stable sets and polynomials. Discrete Mathematics, 124 : 137-153","author":"Lov\u00e1sz L.","year":"1994"},{"key":"e_1_3_2_1_35_1","series-title":"SIAM Journal on Optimization, 1 : 166-190","volume-title":"Cones of matrices and set-functions and 0-1 optimization","author":"Lov\u00e1sz L.","year":"1991"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.111"},{"key":"e_1_3_2_1_37_1","volume-title":"January, 2020","author":"Part Fedor","year":"2020"},{"key":"e_1_3_2_1_38_1","series-title":"SIAM Journal on Computing, 37 ( 3 ): 845-869","volume-title":"Lower bounds for lov\u00e1szschrijver systems and beyond follow from multiparty communication complexity","author":"Paul Beame Toniann Pitassi","year":"2007"},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Pitassi Toniann","year":"1998"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2984450.2984455"},{"key":"e_1_3_2_1_41_1","series-title":"London Math","first-page":"197","volume-title":"Sets and proofs (Leeds","author":"Pudl\u00e1k Pavel","year":"1997"},{"key":"e_1_3_2_1_42_1","volume-title":"Positive polynomials on compact semi-algebraic sets","author":"Putinar Mihai","year":"1993"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_3_2_1_45_1","first-page":"3","volume":"5","author":"Shpilka Amir","year":"2010","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_1_46_1","volume-title":"\u201cNP\u2260P?\". Duke Math. J., 81 : 47-54","author":"Shub Michael","year":"1995"},{"key":"e_1_3_2_1_47_1","volume-title":"Mathematical problems for the next century. The Mathematical Intelligencer, 20 ( 2 ): 7-15","author":"Smale Steve","year":"1998"},{"key":"e_1_3_2_1_48_1","volume-title":"A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207 ( 2 ): 87-97","author":"Stengle Gilbert","year":"1974"},{"key":"e_1_3_2_1_49_1","first-page":"182","volume":"264","author":"Strassen Volker","year":"1973","journal-title":"Angew. Math."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_52_1","volume-title":"Logic and Algorithmic: International Symposium in honour of Ernst Specker, 30 : 365-380","author":"Valiant Leslie G.","year":"1982"}],"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\/pdf\/10.1145\/3357713.3384245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,2]],"date-time":"2022-01-02T15:54:58Z","timestamp":1641138898000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":51,"alternative-id":["10.1145\/3357713.3384245","10.1145\/3357713"],"URL":"http:\/\/dx.doi.org\/10.1145\/3357713.3384245","relation":{},"published":{"date-parts":[[2020,6,22]]}}}