{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:50Z","timestamp":1725664310304},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615507"},{"type":"electronic","value":"9783540705970"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61550-4_173","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:55:31Z","timestamp":1330275331000},"page":"494-505","source":"Crossref","is-referenced-by-count":4,"title":["Approximating good simultaneous Diophantine approximations is almost NP-hard"],"prefix":"10.1007","author":[{"given":"Carsten","family":"R\u00f6ssner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Pierre","family":"Seifert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"38_CR1","volume-title":"Ph.D. thesis","author":"S. Arora","year":"1994","unstructured":"S. Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems. Ph.D. thesis, University of California at Berkeley, 1994."},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern and Z Sweedyk. The hardness of approximate optima in lattices, codes and systems of linear equations. In Proc. 34th IEEE Symp. on Foundations of Computer Science, pages 724\u2013730, 1993.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"38_CR3","unstructured":"S. Arora and C. Lund. Hardness of approximation. In D. Hochbaum (editor), Approximation Algorithms for NP-hard problems, Chapter 11. PWS Publ., 1996."},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"G. Ausiello, P. Crescenzi and M. Protasi. Approximate solutions of NP optimization problems. Theoretical Computer Science, Volume 150, pages1\u201355, 1995.","journal-title":"Theoretical Computer Science"},{"key":"38_CR6","unstructured":"P. Crescenzi and V. Kann. A list of NP-complete optimization problems. Surveys on complexity, Electronic Colloqium on Computational Complexity, http:\/\/www.informatik.uni-trier.de\/eccc\/, 1996."},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"U. Feige and L. Lov\u00e1sz. Two-prover one-round proof systems: Their power and their problems. In Proc. 24th ACM Symp. Theory of Computing, pages 643\u2013654, 1992.","DOI":"10.1145\/129712.129783"},{"key":"38_CR8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A. Frank","year":"1987","unstructured":"A. Frank and \u00c9. Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorial, Volume 7, pages 49\u201365, 1987.","journal-title":"Combinatorial"},{"key":"38_CR9","first-page":"22","volume":"389","author":"D. R. Heath-Brown","year":"1988","unstructured":"D. R. Heath-Brown. The number of primes in a short interval. J. reine angew. Math., Volume 389, pages 22\u201363, 1988.","journal-title":"J. reine angew. Math."},{"key":"38_CR10","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02139702","volume":"55","author":"D. R. Heath-Brown","year":"1979","unstructured":"D. R. Heath-Brown and H. Iwaniec. On the difference between consecutive primes. Inventiones math., Volume 55, pages 49\u201369, 1979.","journal-title":"Inventiones math."},{"key":"38_CR11","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1090\/S0025-5718-1988-0917831-4","volume":"50","author":"R. Kannan","year":"1988","unstructured":"R. Kannan, A. K. Lenstra and L. Lov\u00e1sz. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers. Math. Comp., Volume 50, pages 235\u2013250, 1988.","journal-title":"Math. Comp."},{"key":"38_CR12","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"J. C. Lagarias","year":"1985","unstructured":"J. C. Lagarias. The computational complexity of simultaneous diophantine approximation problems. SIAM J. Comput., Volume 14, pages 196\u2013209, 1985.","journal-title":"SIAM J. Comput."},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"B. S. Majewski and G. Havas. The complexity of greatest common divisor computations. In Proc. 1st International Symposium on Algorithmic Number Theory, pages 184\u2013193. Springer, 1994. LNCS 877.","DOI":"10.1007\/3-540-58691-1_56"},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"R. Raz. A parallel repetition theorem. In Proc. 27th ACM Symp. Theory of Computing, pages 447\u2013456, 1995.","DOI":"10.1145\/225058.225181"},{"key":"38_CR15","doi-asserted-by":"crossref","unstructured":"C. R\u0151ssner and J.-P. Seifert. The complexity of approximate optima for greatest common divisor computations. In Proc. 2nd Algorithmic Number Theory Symposium, pages ?-? Springer, 1996. LNCS.","DOI":"10.1007\/3-540-61581-4_64"},{"key":"38_CR16","unstructured":"C. R\u0151ssner and J.-P. Seifert. On the hardness of approximating shortest integer relations among rational numbers. In Proc. CATS'96 (Computing: The Australasian Theory Symposium), pages 180\u2013186, 1996."},{"key":"38_CR17","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1090\/dimacs\/013\/10","volume":"13","author":"C. P. Schnorr","year":"1993","unstructured":"C. P. Schnorr. Factoring integers and computing discrete logarithms via diophantine approximations. AMS DIM ACS Series in Disc. Math. and Theoretical Comp. Science, Volume 13, pages 171\u2013181, 1993.","journal-title":"AMS DIM ACS Series in Disc. Math. and Theoretical Comp. Science"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"A. Schoenhage. Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm. In 11th ICALP, pages 436\u2013447. Springer, 1987. LNCS 172.","DOI":"10.1007\/3-540-13345-3_40"},{"key":"38_CR19","unstructured":"P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math. Inst., University of Amsterdam, 1981."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1996"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61550-4_173.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:07:47Z","timestamp":1605629267000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61550-4_173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615507","9783540705970"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-61550-4_173","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}