{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:35:19Z","timestamp":1762324519383,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1812240","CCF-1900881","DMS-1757872","DMS-1460766","CCF-1409020"],"award-info":[{"award-number":["DMS-1812240","CCF-1900881","DMS-1757872","DMS-1460766","CCF-1409020"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,8]]},"DOI":"10.1145\/3326229.3326267","type":"proceedings-article","created":{"date-parts":[[2019,7,9]],"date-time":"2019-07-09T12:53:20Z","timestamp":1562676800000},"page":"323-330","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Faster Solution to Smale's 17th Problem I"],"prefix":"10.1145","author":[{"given":"Grigoris","family":"Paouris","sequence":"first","affiliation":[{"name":"Texas A&M University, College Station, TX, USA"}]},{"given":"Kaitlyn","family":"Phillipson","sequence":"additional","affiliation":[{"name":"St. Edwards University, Austin, TX, USA"}]},{"given":"J. Maurice","family":"Rojas","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station, TX, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Oxford University Press","author":"Jinho Gernot","year":"2011","unstructured":"Gernot Akemann; Jinho Baik; Philippe Di Francesco; The Oxford Handbook of Random Matrix Theory, Oxford University Press, 2011."},{"key":"e_1_3_2_1_2_1","volume-title":"NJ, USA), to appear. Also available as Math ArXiV preprint","author":"Alman Josh","year":"1812","unstructured":"Josh Alman, \"Limits on the Universal Method for Matrix Multiplication,\" proceedings of the 34th Computational Complexity Conference (CCC 2019, July 18--20 in New Brunswick, NJ, USA), to appear. Also available as Math ArXiV preprint 1812.08731 ."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_3_2_1_4_1","first-page":"145","volume-title":"Contemporary Mathematics","author":"Chris Hillar Osbert","year":"2011","unstructured":"Osbert Bastani; Chris Hillar, Dimitar Popov, and J. Maurice Rojas, \"Randomization, Sums of Squares, and Faster Real Root Counting for Tetranomials and Beyond,\" Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 145--166, AMS Press, 2011."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568129"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1389962.1389964"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00630-9"},{"key":"e_1_3_2_1_8_1","first-page":"37","volume-title":"Contemporary Mathematics","author":"Beltr\u00b4an Carlos","year":"2011","unstructured":"Carlos Beltr\u00b4an and Luis M. Pardo, \"Efficient Polynomial System Solving by Numerical Methods,\" in Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 37--60, AMS Press, 2011."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3115486.3115852"},{"issue":"2","key":"e_1_3_2_1_10_1","first-page":"183","article-title":"The Number of Roots of a System of Equations","volume":"9","author":"Bernstein David Naumovich","year":"1975","unstructured":"David Naumovich Bernstein, \"The Number of Roots of a System of Equations,\" Functional Analysis and its Applications (translated from Russian), Vol. 9, No. 2, (1975), pp. 183--185.","journal-title":"Functional Analysis and its Applications (translated from Russian)"},{"key":"e_1_3_2_1_11_1","volume-title":"Random polynomials","author":"Bharucha-Reid A. T.","year":"1986","unstructured":"A. T. Bharucha-Reid and M. Sambandham, Random polynomials, Academic Press, Orland, 1986."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002200050010"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Lenore Blum; Felipe Cucker; Mike Shub; and Steve Smale; Complexity and Real Computation Springer-Verlag 1998.","DOI":"10.5555\/265020"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018814"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1939-07068-7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00126-9"},{"key":"e_1_3_2_1_17_1","first-page":"1785","volume-title":"On a problem posed by Steve Smale,\" Annals of Mathematics","author":"B\u00a8urgisser Peter","year":"2011","unstructured":"Peter B\u00a8urgisser and Felipe Cucker, On a problem posed by Steve Smale,\" Annals of Mathematics, Vol. 174 (2011), Issue 3, pp. 1785--1836."},{"key":"e_1_3_2_1_18_1","first-page":"7","article-title":"Solutions to Systems of Binomial Equations","volume":"28","author":"Chen Tianran","year":"2014","unstructured":"Tianran Chen and Tien-Yien Li, \"Solutions to Systems of Binomial Equations,\" Annales Mathematicae Silesianae 28 (2014), pp. 7--34.","journal-title":"Annales Mathematicae Silesianae"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0609045"},{"key":"e_1_3_2_1_20_1","first-page":"1","volume-title":"Amer. Math. Soc.","author":"Edelman Alan","year":"1995","unstructured":"Alan Edelman and Eric Kostlan, \"How Many Zeros of a Random Polynomial are Real?,\" Bull. Amer. Math. Soc., 32, January (1995), pp. 1--37."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-96-08401-X"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-018-9380-5"},{"key":"e_1_3_2_1_23_1","first-page":"1","article-title":"On the Number of Connected Components of Random Algebraic Hypersurfaces","author":"Fyodorov Yan V.","year":"2015","unstructured":"Yan V. Fyodorov, Antonio Lerario, and Erik Lundberg, \"On the Number of Connected Components of Random Algebraic Hypersurfaces,\" J. Geom. Phys. (2015), pp. 1--20.","journal-title":"J. Geom. Phys. ("},{"key":"e_1_3_2_1_24_1","volume-title":"Linear Algebra, and Differential Forms: A Unified Approach","author":"Hubbard John","year":"2015","unstructured":"John Hubbard and Barbara Burke Hubbard, Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach, 5th edition, Matrix Editions, 2015.","edition":"5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153370"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Askold G. Khovanskii Fewnomials AMS Press Providence Rhode Island 1991.","DOI":"10.1090\/mmono\/088"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Pascal Koiran \"Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties \" Proceedings of the 38th Annual IEEE Computer Society Conference on Foundations of Computer Science (FOCS) Oct. 20--22 1997 ACM Press.","DOI":"10.5555\/795663.796372"},{"key":"e_1_3_2_1_28_1","first-page":"419","volume-title":"CA","author":"Kostlan Eric","year":"1990","unstructured":"Eric Kostlan, \"On the distribution of roots of random polynomials,\" From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990), pp. 419--431, Springer, New York, 1993."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-016-9319-7"},{"key":"e_1_3_2_1_30_1","first-page":"97","volume-title":"Contemporary Mathematics","author":"Lee Tsung-Lin","year":"2011","unstructured":"Tsung-Lin Lee and Tien-Yien Li, \"Mixed volume computation in solving polynomial systems,\" in Randomization, Relaxation, and Complexity in Polynomial Equation Solving, Contemporary Mathematics, vol. 556, pp. 97--112, AMS Press, 2011."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_32_1","first-page":"217","article-title":"On a certain converse of H\u00a8older's inequality II","volume":"33","author":"Leindler L.","year":"1972","unstructured":"L. Leindler, \"On a certain converse of H\u00a8older's inequality II,\" Acta Sci. Math. (Szeged) 33 (1972), pp. 217--223.","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002749"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1991-1066835-2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/21465"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-96-03173-5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-97-03583-1"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(87)90063-4"},{"key":"e_1_3_2_1_39_1","volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","year":"1995","unstructured":"Christos H. Papadimitriou, Computational Complexity, Addison- Wesley, 1995."},{"key":"e_1_3_2_1_40_1","volume-title":"Texas A&M","author":"Phillipson Kaitlyn","year":"2016","unstructured":"Kaitlyn Phillipson, Quantitative Aspects of Sums of Squares and Sparse Polynomial Systems, doctoral dissertation, Texas A&M University, department of mathematics, 2016."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90130-0"},{"key":"e_1_3_2_1_42_1","first-page":"335","article-title":"On logarithmic concave measures and functions","volume":"34","author":"Pr'ekopa A.","year":"1975","unstructured":"A. Pr'ekopa, \"On logarithmic concave measures and functions,\" Acta Sci. Math. (Szeged) 34 (1975), pp. 335--343.","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"e_1_3_2_1_43_1","first-page":"689","volume-title":"Lectures in Applied Mathematics","author":"Rojas J. Maurice","year":"1996","unstructured":"J. Maurice Rojas, \"On the Average Number of Real Roots of Certain Random Sparse Polynomial Systems,\" in The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32, (Jim Renegar, Mike Shub, and Steve Smale eds.), pp. 689-- 699, American Mathematical Society, 1996."},{"key":"e_1_3_2_1_44_1","first-page":"293","volume-title":"Contemporary Mathematics","author":"Rojas J. Maurice","year":"2003","unstructured":"J. Maurice Rojas, \"Why Polyhedra Matter in Non-Linear Equation Solving,\" in: Contemporary Mathematics, vol. 334, pp. 293-- 320, American Mathematical Society, 2003."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2004.03.004"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608632"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1530353.1530355"},{"key":"e_1_3_2_1_48_1","first-page":"267","volume-title":"Volumes and Probabilities,\" Computational Algebraic Geometry","author":"Shub Mike","year":"1992","unstructured":"Mike Shub and Steve Smale, \"The Complexity of Bezout's Theorem II: Volumes and Probabilities,\" Computational Algebraic Geometry (F. Eyssette and A. Galligo, Eds.), pp. 267--285, Birkhauser, 1992."},{"key":"e_1_3_2_1_49_1","volume-title":"Introduction to the Theory of Computation","author":"Sipser Michael","year":"2012","unstructured":"Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012.","edition":"3"},{"key":"e_1_3_2_1_50_1","first-page":"185","volume-title":"Wyo.","author":"Smale Steve","year":"1985","unstructured":"Steve Smale, \"Newton's Method Estimates from Data at One Point,\" The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Laramie, Wyo., 1985), pp. 185--196, Springer, New York, 1986."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03025291"},{"key":"e_1_3_2_1_52_1","volume-title":"Amer. Math. Soc.","author":"Smale Steve","year":"2000","unstructured":"Steve Smale, \"Mathematical Problems for the Next Century,\" Mathematics: Frontiers and Perspectives, pp. 271--294, Amer. Math. Soc., Providence, RI, 2000."},{"key":"e_1_3_2_1_53_1","volume-title":"Rational Points on Elliptic Curves, Undergraduate Texts in Mathematics","author":"Joseph","year":"1994","unstructured":"Joseph H. Silverman and John Tate, Rational Points on Elliptic Curves, Undergraduate Texts in Mathematics, Springer, corrected edition, 1994."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1098\/rstl.1861.0016"},{"key":"e_1_3_2_1_55_1","volume-title":"Wampler, \"The Numerical Solution to Systems of Polynomials Arising in Engineering and Science,\" World Scientific","author":"Sommese Andrew J.","year":"2005","unstructured":"Andrew J. Sommese and Charles W. Wampler, \"The Numerical Solution to Systems of Polynomials Arising in Engineering and Science,\" World Scientific, Singapore, 2005."},{"key":"e_1_3_2_1_56_1","volume-title":"Swiss Federal Institute of Technology","author":"Storjohann Arne","year":"2000","unstructured":"Arne Storjohann, \"Algorithms for matrix canonical forms,\" doctoral dissertation, Swiss Federal Institute of Technology, Zurich, 2000."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-09-01252-X"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnu084"},{"key":"e_1_3_2_1_59_1","volume-title":"ACM Press)","author":"Williams Virginia Vassilevska","year":"2014","unstructured":"Virginia Vassilevska Williams, \"Multiplying matrices in time,\" submitted for publication (earlier version in proceedings of STOC 2012 (ACM Symposium on Theory of Computing, May 19--22, NYU), ACM Press), 2014."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1940475.1940524"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1014"}],"event":{"name":"ISSAC '19: International Symposium on Symbolic and Algebraic Computation","sponsor":["SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"],"location":"Beijing China","acronym":"ISSAC '19"},"container-title":["Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326229.3326267","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326229.3326267","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326229.3326267","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:00Z","timestamp":1750206360000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326229.3326267"}},"subtitle":["Real Binomial Systems"],"short-title":[],"issued":{"date-parts":[[2019,7,8]]},"references-count":61,"alternative-id":["10.1145\/3326229.3326267","10.1145\/3326229"],"URL":"https:\/\/doi.org\/10.1145\/3326229.3326267","relation":{},"subject":[],"published":{"date-parts":[[2019,7,8]]},"assertion":[{"value":"2019-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}