Skip to main content
SpringerLink
Log in

Recent directions in algorithmic research

  • Conference paper
  • First Online:
Theoretical Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 104))

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Bibliography

  • Adleman, L. [1979] “A subexponential algorithm for the discrete logarithm problem with applications to cryptography” 20 FOCS 55–60.

    Google Scholar 

  • Adleman, L. [1978] “Two theorems on random polynomial time” 19 FOCS 75–83.

    Google Scholar 

  • Aho, A.V., J.Hopcroft and J.D. Ullman [1974] The design and analysis of computer algorithms, Addison-Wesley.

    Google Scholar 

  • Aleliunas, R., R. Karp, R. Lipton and L. Lovasz [1979] “Random walks, universal sequences, and the complexity of maze problems” 20 FOCS 218–223.

    Google Scholar 

  • Babai, L. [1979] “Monte-Carlo algorithms in graph isomorphism testing” to appear.

    Google Scholar 

  • Baker, T.P., and A.L. Selman [1976] “A second step toward the polynomial hierarchy” 17 FOCS 71–75.

    Google Scholar 

  • Baker, T., J. Gill and R. Solovay [1975] “Relativizations of the P=?NP question” SICOMP 4:4 431–442.

    Google Scholar 

  • Berlekamp, E.R. [1970] “Factoring polynomials over large finite fields” Math Comput. 24 713–735.

    Google Scholar 

  • Blum, M., A. Chandra and M. Wegman [1980] “Equivalence of free Boolean graphs can be decided probabilistically in polynomial time” IPL 10:2 80–82.

    Article  Google Scholar 

  • Borodin, A.B. [1977] “On relating time and space to size and depth” SICOMP 6 733–744.

    Google Scholar 

  • Carter, J.L., and N.M. Wegman [1977] “Universal classes of hashing functions” 9 SIGACT 106–112.

    Google Scholar 

  • Cook, S.A. [1971] “The complexity of theorem proving procedures” 3 SIGACT 151–158.

    Google Scholar 

  • Corneil, D.G., and C.C. Gotlieb [1970] “An efficient algoritnm for graph isomorphism” JACM 17:1 51–64.

    Article  Google Scholar 

  • Diffie and Hellmann [1979] “Privacy and authentication: an introduction to cryptography” Proc. IEEE 67:3.

    Google Scholar 

  • Erdos, P., and J. Spencer [1974] Probabilistic methods in combinatorics, Academic Press.

    Google Scholar 

  • Fischer, M.J., and M.O. Rabin [1974] “Super exponential complexity of Presburger arithmetic” Complexity of Computations (R.M. Karp, ed.) Proceedings of SIAM-AMS symposium in Applied Mathematics.

    Google Scholar 

  • Furst, M., J. Hopcroft and E. Luks [1980] “Polynomial-time algorithms for permutation groups” 21 FOCS 36–41.

    Google Scholar 

  • Gacs and Lovasz [1979] “Khachian's algorithm for linear programming” STAN-CS-79-750 Stanford University.

    Google Scholar 

  • Gill, J. [1977] “Computational complexity of probablistic Turing machines” SICOMP 6:4 675–695.

    Google Scholar 

  • Gobel, F., and A. Jagers [1974] “Random walks on graphs” J. of Stochastic Processes and their Applications 2 311–336.

    Article  Google Scholar 

  • Hoffman, C. [1980] “Testing isomorphism of cone grraphs” 12 SIGACT 244–251.

    Google Scholar 

  • Hopcroft, J., and R. Tarjan [1974] “Efficient planarity testing” JACM 21:4 549–568.

    Article  Google Scholar 

  • Jeroslow, R.G. [1973] “The simplex algorithm with the pivot rule of maximizing criterion improvement” Discrete Math 4 367–377.

    Article  Google Scholar 

  • Karp, R.M., and R.J. Lipton [1980] “Some connections between nonuniform and uniform complexity classes” 12 SIGACT 302–309.

    Google Scholar 

  • Karp, R.M., and C. Papadimitriou [1979] “On linear characterizations of combinatoric optimization problems” 21 FOCS 1–9.

    Google Scholar 

  • Khachian, L.G. [1979] Doklady Akademii Nauk SSSR 244:5 1093–1096.

    Google Scholar 

  • Klee, V., and G. Minty [1972] “How good is the simplex algorithm?” In “Inequalities III” (O. Shisha, ed.) Academic Press 159–175.

    Google Scholar 

  • Knuth, D.E. [1969] The art of computer programming Vol 2, Addison-Wesley.

    Google Scholar 

  • Luks, E. [1980] “Isomorphism of graphs of bounded valence can be tested in polynomial time” 21 FOCS 42–49.

    Google Scholar 

  • Meyer, A.R., and L.J. Stockmeyer [1973] “The equivalence problem for regular expressions with squaring requires exponential space” 13 FOCS 125–129.

    Google Scholar 

  • Miller, G. [1975] “Reimann's hypothesis and test for primality” 7 SIGACT 234–239.

    Google Scholar 

  • Miller, G. [1977] “Graph isomorphism: general remarks” 9 SIGACT 143–150.

    Google Scholar 

  • Pippenger, N.J., and M.J. Fischer [1979] “Relations among complexity measures” JACM 26 361–381.

    Article  Google Scholar 

  • Pratt, V.R. [1975] “Every prime has a succinct certificate” SICOMP 4 214–220.

    Google Scholar 

  • Rabin, M.O. [1976] “Probablistic algoritms,” in J. Traub, ed., Algorithms and Complexity, Academic Press, New York 1976.

    Google Scholar 

  • Rabin, M.O. [1979] “Digitalized Signatures and Public-Key Functions as Intractable as Factorization” MIT/LCS/TR-212.

    Google Scholar 

  • Rabin, M.O. [1980] “Probabilistic algorithms in finite fields” SICOMP 9:2 273–280.

    Google Scholar 

  • Rivest, R.L., A. Shamir and L. Adleman [1978] “On digital signatures and public-key cryptosystems” CACM 21:2 120–126.

    Google Scholar 

  • Schwartz, J.T. [1980] “Fast probabilistic algorithms for verification of polynomial identities” JACM 27:4 701–717.

    Article  Google Scholar 

  • Shanks, D. [1962] Number theory, Chelsea Publishing Company, New York.

    Google Scholar 

  • Sims, C. [1978] “Some group-theorectic algorithms” Lecture notes in math 697 Springer-Verlag, Berlin 108–124.

    Google Scholar 

  • Solovay, R., and V. Strassen [1977] “A fast Monte-Carlo test for primality” SICOMP 6:1 84–85.

    Google Scholar 

  • Solovay, R., and V. Strassen [1978] “Erratum: A fast monte-carlo test for primality” SICOMP 7:1 118.

    Google Scholar 

  • Stockmeyer, L.J. [1976] “The polynomial-time hierarchy” TCS 3:1 1–22.

    Article  Google Scholar 

  • Strassen, V. [1969] “Guassian elimination is not optimal” Numerische Mathematik 13, 354–356.

    Article  Google Scholar 

  • Wegman, M.N., and J.L. Carter [1979] “New classes and applications of hash functions” 20 FOCS 175–182.

    Google Scholar 

  • Yao, A.C. [1977] “Probablistic computations: Toward a unified measure of complexity” 18 FOCS 222–227.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Cornell University, 14853, Ithaca, New York, USA

    John Hopcroft

Authors
  1. John Hopcroft
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Peter Deussen

Rights and permissions

Reprints and permissions

Copyright information

© 1981 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hopcroft, J. (1981). Recent directions in algorithmic research. In: Deussen, P. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017304

Download citation

  • DOI: https://doi.org/10.1007/BFb0017304

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10576-3

  • Online ISBN: 978-3-540-38561-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation