{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:40:03Z","timestamp":1736109603459,"version":"3.32.0"},"publisher-location":"Berlin\/Heidelberg","reference-count":47,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354010576X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0017304","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:22:34Z","timestamp":1132644154000},"page":"123-134","source":"Crossref","is-referenced-by-count":6,"title":["Recent directions in algorithmic research"],"prefix":"10.1007","author":[{"given":"John","family":"Hopcroft","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L. [1979] \u201cA subexponential algorithm for the discrete logarithm problem with applications to cryptography\u201d 20 FOCS 55\u201360.","DOI":"10.1109\/SFCS.1979.2"},{"key":"16_CR2","unstructured":"Adleman, L. [1978] \u201cTwo theorems on random polynomial time\u201d 19 FOCS 75\u201383."},{"key":"16_CR3","unstructured":"Aho, A.V., J.Hopcroft and J.D. Ullman [1974] The design and analysis of computer algorithms, Addison-Wesley."},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., R. Karp, R. Lipton and L. Lovasz [1979] \u201cRandom walks, universal sequences, and the complexity of maze problems\u201d 20 FOCS 218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"16_CR5","unstructured":"Babai, L. [1979] \u201cMonte-Carlo algorithms in graph isomorphism testing\u201d to appear."},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Baker, T.P., and A.L. Selman [1976] \u201cA second step toward the polynomial hierarchy\u201d 17 FOCS 71\u201375.","DOI":"10.1109\/SFCS.1976.2"},{"issue":"4","key":"16_CR7","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., J. Gill and R. Solovay [1975] \u201cRelativizations of the P=?NP question\u201d SICOMP 4:4 431\u2013442.","journal-title":"SICOMP"},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"E.R. Berlekamp","year":"1970","unstructured":"Berlekamp, E.R. [1970] \u201cFactoring polynomials over large finite fields\u201d Math Comput. 24 713\u2013735.","journal-title":"Math Comput."},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","volume":"10","author":"M. Blum","year":"1980","unstructured":"Blum, M., A. Chandra and M. Wegman [1980] \u201cEquivalence of free Boolean graphs can be decided probabilistically in polynomial time\u201d IPL 10:2 80\u201382.","journal-title":"IPL"},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A.B. Borodin","year":"1977","unstructured":"Borodin, A.B. [1977] \u201cOn relating time and space to size and depth\u201d SICOMP 6 733\u2013744.","journal-title":"SICOMP"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Carter, J.L., and N.M. Wegman [1977] \u201cUniversal classes of hashing functions\u201d 9 SIGACT 106\u2013112.","DOI":"10.1145\/800105.803400"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Cook, S.A. [1971] \u201cThe complexity of theorem proving procedures\u201d 3 SIGACT 151\u2013158.","DOI":"10.1145\/800157.805047"},{"issue":"1","key":"16_CR13","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/321556.321562","volume":"17","author":"D.G. Corneil","year":"1970","unstructured":"Corneil, D.G., and C.C. Gotlieb [1970] \u201cAn efficient algoritnm for graph isomorphism\u201d JACM 17:1 51\u201364.","journal-title":"JACM"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Diffie and Hellmann [1979] \u201cPrivacy and authentication: an introduction to cryptography\u201d Proc. IEEE 67:3.","DOI":"10.1109\/PROC.1979.11256"},{"key":"16_CR15","unstructured":"Erdos, P., and J. Spencer [1974] Probabilistic methods in combinatorics, Academic Press."},{"key":"16_CR16","unstructured":"Fischer, M.J., and M.O. Rabin [1974] \u201cSuper exponential complexity of Presburger arithmetic\u201d Complexity of Computations (R.M. Karp, ed.) Proceedings of SIAM-AMS symposium in Applied Mathematics."},{"key":"16_CR17","first-page":"36","volume":"21","author":"M. Furst","year":"1980","unstructured":"Furst, M., J. Hopcroft and E. Luks [1980] \u201cPolynomial-time algorithms for permutation groups\u201d 21 FOCS 36\u201341.","journal-title":"Polynomial-time algorithms for permutation groups\u201d"},{"key":"16_CR18","unstructured":"Gacs and Lovasz [1979] \u201cKhachian's algorithm for linear programming\u201d STAN-CS-79-750 Stanford University."},{"issue":"4","key":"16_CR19","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J. [1977] \u201cComputational complexity of probablistic Turing machines\u201d SICOMP 6:4 675\u2013695.","journal-title":"SICOMP"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-4149(74)90001-5","volume":"2","author":"F. Gobel","year":"1974","unstructured":"Gobel, F., and A. Jagers [1974] \u201cRandom walks on graphs\u201d J. of Stochastic Processes and their Applications 2 311\u2013336.","journal-title":"J. of Stochastic Processes and their Applications"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Hoffman, C. [1980] \u201cTesting isomorphism of cone grraphs\u201d 12 SIGACT 244\u2013251.","DOI":"10.1145\/800141.804672"},{"issue":"4","key":"16_CR22","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., and R. Tarjan [1974] \u201cEfficient planarity testing\u201d JACM 21:4 549\u2013568.","journal-title":"JACM"},{"key":"16_CR23","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90171-4","volume":"4","author":"R.G. Jeroslow","year":"1973","unstructured":"Jeroslow, R.G. [1973] \u201cThe simplex algorithm with the pivot rule of maximizing criterion improvement\u201d Discrete Math 4 367\u2013377.","journal-title":"Discrete Math"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M., and R.J. Lipton [1980] \u201cSome connections between nonuniform and uniform complexity classes\u201d 12 SIGACT 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Karp, R.M., and C. Papadimitriou [1979] \u201cOn linear characterizations of combinatoric optimization problems\u201d 21 FOCS 1\u20139.","DOI":"10.1109\/SFCS.1980.29"},{"issue":"5","key":"16_CR26","first-page":"1093","volume":"244","author":"L.G. Khachian","year":"1979","unstructured":"Khachian, L.G. [1979] Doklady Akademii Nauk SSSR 244:5 1093\u20131096.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"16_CR27","unstructured":"Klee, V., and G. Minty [1972] \u201cHow good is the simplex algorithm?\u201d In \u201cInequalities III\u201d (O. Shisha, ed.) Academic Press 159\u2013175."},{"key":"16_CR28","unstructured":"Knuth, D.E. [1969] The art of computer programming Vol 2, Addison-Wesley."},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Luks, E. [1980] \u201cIsomorphism of graphs of bounded valence can be tested in polynomial time\u201d 21 FOCS 42\u201349.","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., and L.J. Stockmeyer [1973] \u201cThe equivalence problem for regular expressions with squaring requires exponential space\u201d 13 FOCS 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"Miller, G. [1975] \u201cReimann's hypothesis and test for primality\u201d 7 SIGACT 234\u2013239.","DOI":"10.1145\/800116.803773"},{"key":"16_CR32","doi-asserted-by":"crossref","unstructured":"Miller, G. [1977] \u201cGraph isomorphism: general remarks\u201d 9 SIGACT 143\u2013150.","DOI":"10.1145\/800105.803404"},{"key":"16_CR33","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N.J. Pippenger","year":"1979","unstructured":"Pippenger, N.J., and M.J. Fischer [1979] \u201cRelations among complexity measures\u201d JACM 26 361\u2013381.","journal-title":"JACM"},{"key":"16_CR34","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0204018","volume":"4","author":"V.R. Pratt","year":"1975","unstructured":"Pratt, V.R. [1975] \u201cEvery prime has a succinct certificate\u201d SICOMP 4 214\u2013220.","journal-title":"SICOMP"},{"key":"16_CR35","volume-title":"Algorithms and Complexity","author":"M.O. Rabin","year":"1976","unstructured":"Rabin, M.O. [1976] \u201cProbablistic algoritms,\u201d in J. Traub, ed., Algorithms and Complexity, Academic Press, New York 1976."},{"key":"16_CR36","unstructured":"Rabin, M.O. [1979] \u201cDigitalized Signatures and Public-Key Functions as Intractable as Factorization\u201d MIT\/LCS\/TR-212."},{"issue":"2","key":"16_CR37","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1137\/0209024","volume":"9","author":"M.O. Rabin","year":"1980","unstructured":"Rabin, M.O. [1980] \u201cProbabilistic algorithms in finite fields\u201d SICOMP 9:2 273\u2013280.","journal-title":"SICOMP"},{"issue":"2","key":"16_CR38","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R.L. Rivest","year":"1978","unstructured":"Rivest, R.L., A. Shamir and L. Adleman [1978] \u201cOn digital signatures and public-key cryptosystems\u201d CACM 21:2 120\u2013126.","journal-title":"CACM"},{"issue":"4","key":"16_CR39","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T. [1980] \u201cFast probabilistic algorithms for verification of polynomial identities\u201d JACM 27:4 701\u2013717.","journal-title":"JACM"},{"key":"16_CR40","volume-title":"Number theory","author":"D. Shanks","year":"1962","unstructured":"Shanks, D. [1962] Number theory, Chelsea Publishing Company, New York."},{"key":"16_CR41","series-title":"Lecture notes in math","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/BFb0103126","volume-title":"Some group-theorectic algorithms","author":"C. Sims","year":"1978","unstructured":"Sims, C. [1978] \u201cSome group-theorectic algorithms\u201d Lecture notes in math 697 Springer-Verlag, Berlin 108\u2013124."},{"issue":"1","key":"16_CR42","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"Solovay, R., and V. Strassen [1977] \u201cA fast Monte-Carlo test for primality\u201d SICOMP 6:1 84\u201385.","journal-title":"SICOMP"},{"issue":"1","key":"16_CR43","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/0207009","volume":"7","author":"R. Solovay","year":"1978","unstructured":"Solovay, R., and V. Strassen [1978] \u201cErratum: A fast monte-carlo test for primality\u201d SICOMP 7:1 118.","journal-title":"SICOMP"},{"issue":"1","key":"16_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.J. [1976] \u201cThe polynomial-time hierarchy\u201d TCS 3:1 1\u201322.","journal-title":"TCS"},{"key":"16_CR45","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V. [1969] \u201cGuassian elimination is not optimal\u201d Numerische Mathematik 13, 354\u2013356.","journal-title":"Numerische Mathematik"},{"key":"16_CR46","doi-asserted-by":"crossref","unstructured":"Wegman, M.N., and J.L. Carter [1979] \u201cNew classes and applications of hash functions\u201d 20 FOCS 175\u2013182.","DOI":"10.1109\/SFCS.1979.26"},{"key":"16_CR47","doi-asserted-by":"crossref","unstructured":"Yao, A.C. [1977] \u201cProbablistic computations: Toward a unified measure of complexity\u201d 18 FOCS 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017304.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T20:05:17Z","timestamp":1736107517000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354010576X"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/bfb0017304","relation":{},"subject":[]}}