乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T00:47:03Z","timestamp":1723337223308},"reference-count":45,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5951,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1006\/jcss.1997.1472","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T13:06:47Z","timestamp":1033996007000},"page":"317-331","source":"Crossref","is-referenced-by-count":198,"title":["The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations"],"prefix":"10.1006","volume":"54","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[]},{"given":"L\u00e1szl\u00f3","family":"Babai","sequence":"additional","affiliation":[]},{"given":"Jacques","family":"Stern","sequence":"additional","affiliation":[]},{"given":"Z","family":"Sweedyk","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1006\/jcss.1997.1472_SS971472RF1","unstructured":"N. Alon, U. Feige, A. Wigderson, D. Zuckerman, 1933, Dereandomized Graph Products"},{"key":"10.1006\/jcss.1997.1472_SS971472RF2A","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(94)00254-G","article-title":"The complexity and approximability of finding maximum feasible subsystems of linear relations","volume":"147","author":"Amaldi","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1006\/jcss.1997.1472_SS971472RF2B","unstructured":"Proceedings STACS, 1994"},{"key":"10.1006\/jcss.1997.1472_SS971472RF3","unstructured":"E. Amaldi, V. Kann, 1995, On the Approximability of Some NP-Hard Minimization Problems for Linear Systems, Cornell Computational Optimization Project, Cornell University, Ithaca, NY"},{"key":"10.1006\/jcss.1997.1472_SS971472RF4","unstructured":"S. Arora, 1996, Inapproximability result for nearest vector problem inl\u221e"},{"key":"10.1006\/jcss.1997.1472_SS971472RF5","series-title":"Approximation Algorithms for NP-hard Problems","article-title":"Hardness of approximations","author":"Arora","year":"1996"},{"key":"10.1006\/jcss.1997.1472_SS971472RF6","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Matwani, M. Sudan, M. Szegedy, 1992, Proof verification and intractability of approximation problems, Proceedings, 33rd IEEE Symp. on Foundations of Computer Science","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10.1006\/jcss.1997.1472_SS971472RF7","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Safra, 1992, Probabilistic checking of proofs: A new characterization of NP, Proceedings 33rd IEEE Symp. on Foundations of Computer Science","DOI":"10.1109\/SFCS.1992.267824"},{"key":"10.1006\/jcss.1997.1472_SS971472RF8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz's lattice reduction and the nearest lattice point problem","volume":"6","author":"Babai","year":"1986","journal-title":"Combinatorica"},{"key":"10.1006\/jcss.1997.1472_SS971472RF9","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, M. Szegedy, 1992, Checking computations in polylogarithmic time, Proceedings, 23rd Symp. on Theory of Computing","DOI":"10.1145\/103418.103428"},{"key":"10.1006\/jcss.1997.1472_SS971472RF10","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"Babai","year":"1991","journal-title":"Comput. Complexity"},{"key":"10.1006\/jcss.1997.1472_SS971472RF11","unstructured":"M. Bellare, 1992, Interactive Proofs and Approximations"},{"key":"10.1006\/jcss.1997.1472_SS971472RF12","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russell, 1993, Efficient multi-prover interactive proofs with applications to approximation problems, Proceedings 25th ACM Symp. on Theory of Computing","DOI":"10.1145\/195058.195467"},{"key":"10.1006\/jcss.1997.1472_SS971472RF13A","series-title":"Complexity of Numerical Optimization","article-title":"The complexity of approximating non-linear programs","author":"Bellare","year":"1993"},{"key":"10.1006\/jcss.1997.1472_SS971472RF13B","unstructured":"March 1992, IBM Research Report RC 17831"},{"key":"10.1006\/jcss.1997.1472_SS971472RF14","doi-asserted-by":"crossref","unstructured":"M. Ben-or, S. Goldwasser, J. Kilian, A. Wigderson, 1988, Multiprover interactive proofs: How to remove intractability assumptions, Proceedings 20th ACM Symp. on Theory of Computing","DOI":"10.1145\/62212.62223"},{"key":"10.1006\/jcss.1997.1472_SS971472RF15","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","article-title":"On the inherent intractability of certain coding problems","author":"Berlekamp","year":"1978","journal-title":"Trans. Inform. Theory"},{"key":"10.1006\/jcss.1997.1472_SS971472RF16","doi-asserted-by":"crossref","unstructured":"M. Blum, S. Kannan, 1989, Designing programs that check their work, Proceedings 21st ACM Symp. on Theory of Computing","DOI":"10.1145\/73007.73015"},{"key":"10.1006\/jcss.1997.1472_SS971472RF17","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby, R. Rubinfeld, 1990, Self-testing\/correcting with applications to numerical problems, Proceedings 22nd ACM Symp. on Theory of Computing","DOI":"10.1145\/100216.100225"},{"key":"10.1006\/jcss.1997.1472_SS971472RF18","series-title":"Combinatorics","author":"Bollob\u00e1s","year":"1986"},{"key":"10.1006\/jcss.1997.1472_SS971472RF19","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/18.52484","article-title":"The hardness of decoding linear codes with preprocessing","author":"Bruck","year":"1990","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1006\/jcss.1997.1472_SS971472RF20A","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/BF01271372","article-title":"The complexity of the max-word problem and the power of one-way interactive proof systems","volume":"3","author":"Condon","year":"1993","journal-title":"Comput. Complexity"},{"key":"10.1006\/jcss.1997.1472_SS971472RF20B","series-title":"Proc. 8th Symp. on Theor. Aspects of Comp. Sci.","year":"1991"},{"key":"10.1006\/jcss.1997.1472_SS971472RF21","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, M. Szegedy, 1991, Approximating clique is almost NP-complete, Proceedings 32nd IEEE Symp. on Foundations of Computer Science","DOI":"10.1109\/SFCS.1991.185341"},{"key":"10.1006\/jcss.1997.1472_SS971472RF22","doi-asserted-by":"crossref","unstructured":"U. Feige, L. Lov\u00e1sz, 1992, Two-prover one-round proof systems: Their power and their problems, Proc. 24th ACM Symp. on Theory of Computing","DOI":"10.1145\/129712.129783"},{"key":"10.1006\/jcss.1997.1472_SS971472RF23","doi-asserted-by":"crossref","unstructured":"A. Frank, \u00c9. Tardos, 1985, An application of simulta- neous approximation in combinatorial optimization, Proceedings, 26th IEEE Symp. on Foundations of Computer Science","DOI":"10.1109\/SFCS.1985.8"},{"key":"10.1006\/jcss.1997.1472_SS971472RF24","series-title":"Computers and Intractability: A Guide to the theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1006\/jcss.1997.1472_SS971472RF25","doi-asserted-by":"crossref","unstructured":"K-U. Hoeffgen, H-U. Simon, 1992, Robust trainability of single neurons, Proceedings, of the Conference of Learning Theory","DOI":"10.1145\/130385.130431"},{"key":"10.1006\/jcss.1997.1472_SS971472RF26","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","article-title":"The densest hemisphere problem","volume":"6","author":"Johnson","year":"1978","journal-title":"Theor. Comput. Sci."},{"key":"10.1006\/jcss.1997.1472_SS971472RF27","doi-asserted-by":"crossref","DOI":"10.1287\/moor.12.3.415","article-title":"Minkowski's convex body theorem and integer programming","volume":"12","author":"Kannan","year":"1987","journal-title":"Math. Oper. Res."},{"key":"10.1006\/jcss.1997.1472_SS971472RF28","series-title":"Annual Reviews of Computer Science","article-title":"Algorithms geometry of numbers","author":"Kannan","year":"1987"},{"key":"10.1006\/jcss.1997.1472_SS971472RF29","series-title":"Complexity of Computer Computations","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1006\/jcss.1997.1472_SS971472RF30","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF02128669","article-title":"Korkine\u2013Zolotarev bases and successive minima of a lattice and its reciprocal lattice","volume":"10","author":"Lagarias","year":"1990","journal-title":"Combinatorica"},{"key":"10.1006\/jcss.1997.1472_SS971472RF31","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/2455.2461","article-title":"Solving low-density subset-sum problems","volume":"32","author":"Lagarius","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1006\/jcss.1997.1472_SS971472RF32","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"Lenstra","year":"1982","journal-title":"Math. Ann."},{"key":"10.1006\/jcss.1997.1472_SS971472RF33","author":"Lov\u00e1sz","year":"1986","journal-title":"NSF-CBMS Reg. Conference Series"},{"key":"10.1006\/jcss.1997.1472_SS971472RF34A","first-page":"960","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. A. C. M."},{"key":"10.1006\/jcss.1997.1472_SS971472RF34B","unstructured":"1993, 25th STOC"},{"key":"10.1006\/jcss.1997.1472_SS971472RF35","series-title":"Perceptrons","author":"Minsky","year":"1968"},{"key":"10.1006\/jcss.1997.1472_SS971472RF36A","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1006\/jcss.1997.1472_SS971472RF36B","unstructured":"1988, 20th ACM STOC"},{"key":"10.1006\/jcss.1997.1472_SS971472RF37","unstructured":"C. P. Schnorr, 1985, A hierarchy of polynomial-time basis reduction algorithms, Proceedings, Conf. on Algorithms, P\u00e9cs, Hungary, Lov\u00e1szSzemer\u00e9di, North-Holland, Amsterdam"},{"key":"10.1006\/jcss.1997.1472_SS971472RF38","unstructured":"J. Stern, Approximating the number of error locations is NP-complete, Proceedings, AAECC-10"},{"key":"10.1006\/jcss.1997.1472_SS971472RF39","unstructured":"P. van Emde Boas, 1981, Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice, Math. Inst. Univ. Amsterdam"},{"key":"10.1006\/jcss.1997.1472_SS971472RF40","unstructured":"D. Zuckerman, NP-complete problems have a version that's hard to approximate, 8th Structure in Complexity Theory Conf. 1993"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000097914720?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000097914720?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T13:18:08Z","timestamp":1576588688000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000097914720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["S0022000097914720"],"URL":"https:\/\/doi.org\/10.1006\/jcss.1997.1472","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}