{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T13:17:12Z","timestamp":1772716632598,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1997,6,1]],"date-time":"1997-06-01T00:00:00Z","timestamp":865123200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,6,1]],"date-time":"1997-06-01T00:00:00Z","timestamp":865123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Global Optimization"],"published-print":{"date-parts":[[1997,6]]},"DOI":"10.1023\/a:1008203903341","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T13:47:34Z","timestamp":1040564854000},"page":"351-365","source":"Crossref","is-referenced-by-count":62,"title":["On the Complexity of Semidefinite Programs"],"prefix":"10.1007","volume":"10","author":[{"given":"Lorant","family":"Porkolab","sequence":"first","affiliation":[]},{"given":"Leonid","family":"Khachiyan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"124788_CR1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF01582137","volume":"61","author":"I. Adler","year":"1993","unstructured":"Adler, I. and Shamir, R. (1990), A Randomized Scheme for Speeding Up Algorithms for Linear and Convex Quadratic Programming Problems with a High Constraints-to-Variables Ratio, Math. Programming\n61 (1993), 39\u201352.","journal-title":"Math. Programming"},{"key":"124788_CR2","unstructured":"Chazelle, B. and Matousek, J. (1993), On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension, Proc. of the 4th ACM-SIAM Symp. on Discrete Algorithms, 281\u2013290."},{"key":"124788_CR3","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"K.L. Clarkson","year":"1995","unstructured":"Clarkson, K.L. (1995), Las Vegas Algorithms for Linear and Integer Programming When the Dimension Is Small, J. of ACM\n42 (1995), 488\u2013499.","journal-title":"J. of ACM"},{"key":"124788_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L. and Schrijver, A. (1988), Geometric Algorithms and Combinatorial Optimization, Springer, Berlin."},{"key":"124788_CR5","volume-title":"Computer Algebra, Symbolic and Algebraic Computation (Second Edition)","author":"M. Mignotte","year":"1982","unstructured":"Mignotte, M. (1982), Some Useful Bounds, in Buchberger, B., Collins, G.E., and Loos, R. (eds.) in cooperation with Albrecht, R., Computer Algebra, Symbolic and Algebraic Computation (Second Edition), Springer, Wien."},{"key":"124788_CR6","volume-title":"An AlgorithmicAnalysis of Multiquadratic and Semidefinite Programming Problems","author":"M.V. Ramana","year":"1993","unstructured":"Ramana, M.V. (1993) An AlgorithmicAnalysis of Multiquadratic and Semidefinite Programming Problems, Ph.D. Thesis, The Johns Hopkins University, Baltimore."},{"key":"124788_CR7","unstructured":"Ramana, M.V. (1995) An Exact Duality Theory for Semidefinite Programming and its Complexity Implications, DIMACS Technical Report 95-02."},{"key":"124788_CR8","doi-asserted-by":"crossref","first-page":"1008","DOI":"10.1137\/0221060","volume":"21","author":"J. Renegar","year":"1992","unstructured":"Renegar, J. (1992a) On the Computational Complexity of Approximating Solutions for Real Algebraic Formulae, SIAM J. on Computing\n21 (1992), 1008\u20131025.","journal-title":"SIAM J. on Computing"},{"key":"124788_CR9","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J. (1992b) On the Computational Complexity and Geometry of the First Order Theory of the Reals. Part I: Introduction; Preliminaries; the Geometry of Semi-Algebraic Sets; the Decision Problem for the Existential Theory of the Reals, J. of Symbolic Computation\n13 (1992), 255\u2013299.","journal-title":"J. of Symbolic Computation"},{"key":"124788_CR10","doi-asserted-by":"crossref","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"T.R. Rockafellar","year":"1970","unstructured":"Rockafellar, T.R., Convex Analysis, Princeton University Press, NJ, 1970."},{"key":"124788_CR11","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A. (1986) Theory of Linear and Integer Programming, Wiley, New York."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008203903341.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1008203903341\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1008203903341.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:41:31Z","timestamp":1751366491000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1008203903341"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,6]]}},"alternative-id":["124788"],"URL":"https:\/\/doi.org\/10.1023\/a:1008203903341","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}