{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:44:42Z","timestamp":1725493482912},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664086"},{"type":"electronic","value":"9783540483403"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48340-3_10","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T17:04:52Z","timestamp":1184605492000},"page":"103-113","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of the Extended GCD Problem"],"prefix":"10.1007","author":[{"given":"George","family":"Havas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Pierre","family":"Seifert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317\u2013331, April 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR2","unstructured":"S. Arora and C. Lund. Hardness of approximation. In D. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, chapter 11. PWS Publishing, 1996."},{"key":"10_CR3","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, 150:1\u201355, 1995.","journal-title":"Theoretical Computer Science"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"L. Babai. Trading group theory for randomness. In Proc. 17th Ann. ACM Symp. on Theory of Computing, pages 421\u2013429, 1985.","DOI":"10.1145\/22145.22192"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L. Babai","year":"1986","unstructured":"L. Babai. On Lovasz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica, 6:1\u201313, 1986.","journal-title":"Combinatorica"},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"R. Boppana, J. H\u00e5stad, and S. Zachos. Does coNP have short interactive proofs? Information Processing Letters, 25(2):127\u2013132, 1987.","journal-title":"Information Processing Letters"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"O. Goldreich and S. Goldwasser. On the limits of non-approximability of lattice problems. In Proc. 30th ACM Symp. Theory of Computing, pages 1\u20139, 1998.","DOI":"10.1145\/276698.276704"},{"issue":"l","key":"10_CR8","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(l):186\u2013208, February 1989.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR9","unstructured":"S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. Advances in Computing Research 5: Randomness and Computation, 1989."},{"key":"10_CR10","first-page":"184","volume":"105","author":"G. Havas","year":"1994","unstructured":"G. Havas and B. S. Majewski. Hermite normal form computation for integer matrices. Congressus Numerantium, 105:184\u2013193, 1994.","journal-title":"Congressus Numerantium"},{"key":"10_CR11","first-page":"104","volume":"111","author":"G. Havas","year":"1995","unstructured":"G. Havas and B. S. Majewski. Extended gcd calculation. Congressus Numerantium, 111:104\u2013114, 1995.","journal-title":"Congressus Numerantium"},{"key":"10_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/BFb0015426","volume-title":"Algorithms and Computation","author":"G. Havas","year":"1995","unstructured":"G. Havas and B. S. Majewski. A hard problem which is almost always easy. In Algorithms and Computation, Lecture Notes in Computer Science 1004, 216\u2013223, 1995."},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1006\/jsco.1996.0141","volume":"24","author":"G. Havas","year":"1997","unstructured":"G. Havas and B.S. Majewski. Integer matrix diagonalization. Journal of Symbolic Computation, 24:399\u2013408, 1997.","journal-title":"Journal of Symbolic Computation"},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1080\/10586458.1998.10504362","volume":"7","author":"G. Havas","year":"1998","unstructured":"G. Havas, B. S. Majewski and K. R. Matthews. Extended gcd and Hermite normal form algorithms via lattice basis reduction. Experimental Mathematics, 7:125\u2013136, 1998.","journal-title":"Experimental Mathematics"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1137\/0218045","volume":"18","author":"C. S. Iliopoulos","year":"1989","unstructured":"C. S. Iliopoulos. Worst case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix. SIAM Journal on Computing, 18:658\u2013669, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/322358.322368","volume":"30","author":"R. Kannan","year":"1983","unstructured":"R. Kannan. Polynomial-time aggregation of integer programming problems. J. ACM, 30:133\u2013145, 1983.","journal-title":"J. ACM"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan and L. Trevisan. Constraint Satisfaction: The Approximability of Minimization Problems. In Proceedings of the 12th IEEE Conference on Computational Complexity, pages 282\u2013296, 1997.","DOI":"10.1109\/CCC.1997.612323"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of minimization problems. J. ACM, 41:960\u2013981, 1994.","journal-title":"J. ACM"},{"key":"10_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/3-540-58691-1_56","volume-title":"Algorithmic Number Theory","author":"B. S. Majewski","year":"1994","unstructured":"B. S. Majewski and G. Havas. The complexity of greatest common divisor computations. In Algorithmic Number Theory, pages 184\u2013193. Springer, 1994. LNCS 877."},{"issue":"3","key":"10_CR20","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763\u2013803, June 1998.","journal-title":"SIAM Journal on Computing"},{"key":"10_CR21","series-title":"Lect Notes Comput Sci","first-page":"184","volume-title":"Algorithmic Number Theory","author":"C. R\u00f6ssner","year":"1996","unstructured":"C. R\u00f6ssner and J.-P. Seifert. The complexity of approximate optima for greatest common divisor computations. In Algorithmic Number Theory, pages 184\u2013193. Springer, 1996. LNCS 1122."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1999"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48340-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T16:56:03Z","timestamp":1548348963000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48340-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664086","9783540483403"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-48340-3_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}