{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:30:24Z","timestamp":1773228624761,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2009,8,3]],"date-time":"2009-08-03T00:00:00Z","timestamp":1249257600000},"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":[[2009,8,3]]},"DOI":"10.1145\/1577190.1577212","type":"proceedings-article","created":{"date-parts":[[2009,9,25]],"date-time":"2009-09-25T19:37:20Z","timestamp":1253907440000},"page":"133-142","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimization and NP_R-completeness of certain fewnomials"],"prefix":"10.1145","author":[{"given":"Philippe P.","family":"P\u00e9bay","sequence":"first","affiliation":[{"name":"Sandia National Laborotories, Livermore, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Maurice","family":"Rojas","sequence":"additional","affiliation":[{"name":"Texas A&M University, College Station, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David C.","family":"Thompson","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8,3]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697926"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial optimization problems and their approximability properties,\" Springer-Verlag","author":"Ausiello G.","year":"1999","unstructured":"Ausiello , G. ; Crescenzi , P.; Gambosi , G. ; Kann , V. ; Marchetti-Spaccamela , A. and Protasi , M. , \" Complexity and Approximation: Combinatorial optimization problems and their approximability properties,\" Springer-Verlag , 1999 . Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A. and Protasi, M., \"Complexity and Approximation: Combinatorial optimization problems and their approximability properties,\" Springer-Verlag, 1999."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.06.002"},{"key":"e_1_3_2_1_4_1","volume-title":"Maurice, \"Sums of Squares, Randomization, and Sparse Polynomials,\" in preparation","author":"Bastani Hillar","year":"2009","unstructured":"Bastani , Osbert; Hillar , Chris; Popov , Dimitar; and Rojas , J . Maurice, \"Sums of Squares, Randomization, and Sparse Polynomials,\" in preparation , 2009 . Bastani, Osbert; Hillar, Chris; Popov, Dimitar; and Rojas, J. Maurice, \"Sums of Squares, Randomization, and Sparse Polynomials,\" in preparation, 2009."},{"key":"e_1_3_2_1_5_1","volume-title":"Papers from the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science held at","author":"Basu Saugata","year":"2001","unstructured":"Basu , Saugata and Gonzalez-Vega , Laureano , Algorithmic and Quantitative Real Algebraic Geometry , Papers from the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science held at Rutgers University , Piscataway, NJ ( March 12-16, 2001 ), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 60. Basu, Saugata and Gonzalez-Vega, Laureano, Algorithmic and Quantitative Real Algebraic Geometry, Papers from the DIMACS Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science held at Rutgers University, Piscataway, NJ (March 12-16, 2001), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 60."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics","author":"Basu Pollack","year":"2006","unstructured":"Basu , Saugata; Pollack , Ricky; and Roy , Marie-Francoise , Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics , vol. 10 , Springer-Verlag , 2006 . Basu, Saugata; Pollack, Ricky; and Roy, Marie-Francoise, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, 2006."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250809"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576702.1576711"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"Blum Cucker","year":"1998","unstructured":"Blum , Lenore; Cucker , Felipe; Shub , Mike; and Smale , Steve , Complexity and Real Computation , Springer-Verlag , 1998 . Blum, Lenore; Cucker, Felipe; Shub, Mike; and Smale, Steve, Complexity and Real Computation, Springer-Verlag, 1998."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321944"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62257"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.4.609.20520"},{"key":"e_1_3_2_1_14_1","unstructured":"Crofts Evelyn L. and Rojas J. Maurice \"Complex Vertices for A-discriminants and Mixed Volumes \" in progress.  Crofts Evelyn L. and Rojas J. Maurice \"Complex Vertices for A-discriminants and Mixed Volumes \" in progress."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300519"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668791"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.17323\/1609-4514-2007-7-3-425-452"},{"key":"e_1_3_2_1_19_1","volume-title":"Annals of Mathematics Studies, no. 131","author":"Fulton William","year":"1993","unstructured":"Fulton , William , Introduction to Toric Varieties , Annals of Mathematics Studies, no. 131 , Princeton University Press , Princeton, New Jersey, 1993 . Fulton, William, Introduction to Toric Varieties, Annals of Mathematics Studies, no. 131, Princeton University Press, Princeton, New Jersey, 1993."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-007-1025-2_5"},{"key":"e_1_3_2_1_21_1","volume-title":"Birkhüuser","author":"Gel'fand Israel","year":"1994","unstructured":"Gel'fand , Israel Moseyevitch; Kapranov , Misha M.; and Zelevinsky , Andrei V .; Discriminants , Resultants and Multidimensional Determinants , Birkhüuser , Boston , 1994 . Gel'fand, Israel Moseyevitch; Kapranov, Misha M.; and Zelevinsky, Andrei V.; Discriminants, Resultants and Multidimensional Determinants, Birkhüuser, Boston, 1994."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2008.11.003"},{"key":"e_1_3_2_1_23_1","volume-title":"Inequalities, reprint of the 1952 edition","author":"Hardy G. H.","year":"1988","unstructured":"Hardy , G. H. ; Littlewood , J. E.; Pólya, G. , Inequalities, reprint of the 1952 edition , Cambridge Mathematical Library, Cambridge University Press , Cambridge , 1988 . Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities, reprint of the 1952 edition, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1988."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1145768.1145798"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1277548.1277577"},{"key":"e_1_3_2_1_26_1","unstructured":"Khovanski Askold Fewnomials AMS Press Providence Rhode Island 1991.  Khovanski Askold Fewnomials AMS Press Providence Rhode Island 1991."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0502"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-007-9112-2"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064504X"},{"key":"e_1_3_2_1_30_1","volume-title":"Berlin","author":"Jr Hendrik W","year":"1997","unstructured":"Lenstra ( Jr .), Hendrik W . , \" Finding Small Degree Factors of Lacunary Polynomials ,\" Number Theory in Progress , Vol . 1 (Zakopane-Kóscielisko , 1997 ), pp. 267--276, de Gruyter , Berlin , 1999. Lenstra (Jr.), Hendrik W., \"Finding Small Degree Factors of Lacunary Polynomials,\" Number Theory in Progress, Vol. 1 (Zakopane-Kóscielisko, 1997), pp. 267--276, de Gruyter, Berlin, 1999."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2834-8"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276862"},{"key":"e_1_3_2_1_33_1","first-page":"293","volume-title":"Ser. B","author":"Parrilo Pablo A","year":"2003","unstructured":"Parrilo , Pablo A . , \"Semidefinite programming relaxations for semialgebraic problems,\" Algebraic and geometric methods in discrete optimization, Math . Program . 96 ( 2003 ), no. 2 , Ser. B , pp. 293 -- 320 . Parrilo, Pablo A., \"Semidefinite programming relaxations for semialgebraic problems,\" Algebraic and geometric methods in discrete optimization, Math. Program. 96 (2003), no. 2, Ser. B, pp. 293--320."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2004.03.004"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390768.1390781"},{"key":"e_1_3_2_1_36_1","first-page":"565","article-title":"Computation of π using arithmetic-geometric mean","volume":"30","author":"Salamin E.","year":"1976","unstructured":"Salamin , E. , \" Computation of π using arithmetic-geometric mean ,\" Math. Comput. , 30 ( 1976 ), pp. 565 -- 570 . Salamin, E., \"Computation of π using arithmetic-geometric mean,\"Math. Comput., 30 (1976), pp. 565--570.","journal-title":"Math. Comput."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592148"}],"event":{"name":"SNC '09: Symbolic Numeric Computation","location":"Kyoto Japan","acronym":"SNC '09","sponsor":["ACM Association for Computing Machinery","SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"]},"container-title":["Proceedings of the 2009 conference on Symbolic numeric computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1577190.1577212","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1577190.1577212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:43Z","timestamp":1750278163000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1577190.1577212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,3]]},"references-count":37,"alternative-id":["10.1145\/1577190.1577212","10.1145\/1577190"],"URL":"https:\/\/doi.org\/10.1145\/1577190.1577212","relation":{},"subject":[],"published":{"date-parts":[[2009,8,3]]},"assertion":[{"value":"2009-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}