{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T18:57:35Z","timestamp":1781549855530,"version":"3.54.5"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01585569","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:17Z","timestamp":1114677737000},"page":"429-441","source":"Crossref","is-referenced-by-count":44,"title":["The complexity of approximating a nonlinear program"],"prefix":"10.1007","volume":"69","author":[{"given":"Mihir","family":"Bellare","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phillip","family":"Rogaway","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, \u201cProof verification and hardness of approximation problems,\u201d in:Proceedings of the Thirty-Third Annual Symposium on the Foundations of Computer Science, IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra, \u201cProbabilistic checking of proofs; A new characterization of NP,\u201d in:Proceedings of the Thirty-Third Annual Symposium on the Foundations of Computer Science, IEEE, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. D'Atri and M. Protasi, \u201cStructure preserving reductions among convex optimization problems,\u201dJournal of Computer and System Sciences 21 (1980) 136\u2013153.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow and C. Lund, \u201cNon-deterministic exponential time has two-prover interactive protocols,\u201dComputational Complexity 1 (1991) 3\u201340.","journal-title":"Computational Complexity"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai and S. Moran, \u201cArthur-Merlin games: A randomized proof system and a hierarchy of complexity classes,\u201dJournal of Computer and System Sciences 36 (1988) 254\u2013276.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"M. Bellare, \u201cInteractive proofs and approximation: reductions from two provers in one round,\u201d in:Proceedings of the Second Israel Symposium on Theory and Computing Systems, 1993.","DOI":"10.1109\/ISTCS.1993.253462"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund and A. Russell, \u201cEfficient probabilistically checkable proofs and applications to approximation,\u201d in:Proceedings of the Twenty-Fifth Annual Symposium on the Theory of Computing, ACM, 1993.","DOI":"10.1145\/167088.167174"},{"key":"CR8","volume-title":"Complexity of Numerical Optimization","author":"M. Bellare","year":"1993","unstructured":"M. Bellare and P. Rogaway, \u201cThe complexity of approximating a nonlinear program,\u201d in: P.M. Pardalos, ed.Complexity of Numerical Optimization (World Scientific, Singapore, 1993)."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan, \u201cImproved non-approximability results,\u201d in:Proceedings of the Twenty-Sixth Annual Symposium on the Theory of Computing, ACM, 1994.","DOI":"10.1145\/195058.195129"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian and A. Wigderson, \u201cMulti-prover interactive proofs: how to remove intractability assumptions,\u201d in:Proceedings of the Twentieth Annual Symposium on the Theory of Computing, ACM, 1988.","DOI":"10.1145\/62212.62223"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"J. Canny, \u201cSome algebraic and geometric computations in PSPACE,\u201d in:Proceedings of the Twentieth Annual Symposium on the Theory of Computing, ACM, 1988.","DOI":"10.1145\/62212.62257"},{"key":"CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the Eighth Annual Symposium on Theoretical Aspects of Computer Science","author":"A. Condon","year":"1991","unstructured":"A. Condon, \u201cThe complexity of the max word problem and the power of one-way interactive proof systems,\u201d in:Proceedings of the Eighth Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 480 (Springer, Berlin, 1991)."},{"key":"CR13","series-title":"Annals of Discrete Mathematics","first-page":"83","volume-title":"Algebraic and Combinatorial Methods in Operations Research","author":"C. Ebenegger","year":"1984","unstructured":"C. Ebenegger, P. Hammer and D. de Werra, \u201cPseudo-boolean functions and stability of graphs,\u201d inAlgebraic and Combinatorial Methods in Operations Research, Annals of Discrete Mathematics, Vol. 19 (North-Holland, Amsterdam, 1984) 83\u201397."},{"key":"CR14","unstructured":"U. Feige, \u201cNEXPTIME has two-provers one-round proof systems with exponentially small error probability,\u201d Manuscript, 1991."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"U. Feige, \u201cOn the success probability of the two provers in one round proof systems,\u201d in:Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, IEEE, 1991.","DOI":"10.1109\/SCT.1991.160251"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra and M. Szegedy, \u201cApproximating clique is almost NP-complete,\u201d in:Proceedings of the Thirty-Second Annual Symposium on the Foundations of Computer Science, IEEE, 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian, \u201cTwo prover protocols\u2014Low error at affordable rates,\u201d in:Proceedings of the Twenty-Sixth Annual Symposium on the Theory of Computing, ACM, 1994.","DOI":"10.1145\/195058.195128"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"U. Feige and L. Lov\u00e1sz, \u201cTwo-prover one round proof systems: their power and their problems,\u201d in:Proceedings of the Twenty-Fourth Annual Symposium on the Theory of Computing, ACM, 1992.","DOI":"10.1145\/129712.129783"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel and M. Sipser, \u201cOn the power of multiprover interactive protocols,\u201d in:Proceedings of the Third Annual Conference on Structure in Complexity Theory, IEEE, 1988.","DOI":"10.1109\/SCT.1988.5275"},{"issue":"1","key":"CR20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali and C. Rackoff, \u201cThe knowledge complexity of interactive proofs,\u201dSIAM Journal of Computing 18 (1) (1989) 186\u2013208.","journal-title":"SIAM Journal of Computing"},{"key":"CR21","first-page":"1049","volume":"248","author":"M. Kozlov","year":"1979","unstructured":"M. Kozlov, S. Tarasov and L. Ha\u010dijan, \u201cPolynomial solvability of convex quadratic programming,\u201dDoklady Akademii Nauk SSSR 248 (1979) 1049\u20131051; Translation in:Soviet Mathematics Doklady 20 (1979) 1108\u20131111.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"D. Lapidot and A. Shamir, \u201cFully parallelized multi-prover protocols for NEXP-time,\u201d in:Proceedings of the Thirty-Second Annual Symposium on the Foundations of Computer Science, IEEE, 1991.","DOI":"10.1109\/SFCS.1991.185342"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, \u201cOn the hardness of approximating minimization problems,\u201d in:Proceedings of the Twenty-Fifth Annual Symposium on the Theory of Computing, ACM, 1993.","DOI":"10.1145\/167088.167172"},{"key":"CR24","first-page":"533","volume":"11","author":"T. Motzkin","year":"1964","unstructured":"T. Motzkin and E. Straus, \u201cMaxima for graphs and a new proof of a theorem by Tu\u00e1n,\u201dNotices of the American Mathematical Society 11 (1964) 533\u2013540.","journal-title":"Notices of the American Mathematical Society"},{"key":"#cr-split#-CR25.1","unstructured":"A. Nemirovsky and D. Yudin,Slozhnost' Zadach i Effektivnost' Metodov Optimizatsii (1979);"},{"key":"#cr-split#-CR25.2","unstructured":"Translated by E. Dawson asProblem Complexity and Method Efficiency in Optimization (Wiley, New York, 1983)."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S. Sahni","year":"1974","unstructured":"S. Sahni, \u201cComputationally related problems,\u201dSIAM Journal of Computing 3 (1974) 262\u2013279.","journal-title":"SIAM Journal of Computing"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"G. Tardos, \u201cMulti-prover encoding schemes and three prover proof systems,\u201d in:Proceedings of the Ninth Annual Conference on Structure in Complexity Theory, IEEE, 1994.","DOI":"10.1109\/SCT.1994.315793"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90100-C","volume":"36","author":"S. Vavasis","year":"1990","unstructured":"S. Vavasis, \u201cQuadratic programming is in NP,\u201dInformation Processing Letters 36 (1990) 73\u201377.","journal-title":"Information Processing Letters"},{"key":"CR29","unstructured":"S. Vavasis, \u201cApproximation algorithms for indefinite quadratic programming,\u201d TR 91-1228, Dept. of Computer Science, Cornell University, August 1991."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"S. Vavasis, \u201cOn approximation algorithms for concave programming,\u201d in: C.A. Floudas and P.M. Pardalos, eds.,Recent Advances in Global Optimization (Princeton University Press, 1992) pp. 3\u201318.","DOI":"10.1515\/9781400862528.3"},{"key":"CR31","unstructured":"S. Vavasis, \u201cPolynomial time weak approximation algorithms for quadratic programming,\u201d in: P. Pardalos, ed.,Complexity in Numerical Optimization (1992)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585569.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585569\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:47:37Z","timestamp":1586231257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":32,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01585569"],"URL":"https:\/\/doi.org\/10.1007\/bf01585569","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}