John Hopcroft



IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University


Research Interests

The Analysis and Modeling of Large Linked Networks (NSF) Information Forensics (AFOSR)

Selected Publications
  • An approach to a unified theory of automata. BSTJ, Vol. 46:8, October 1967, 1793-1829 (with J. D. Ullman).

  • On the equivalence and containment problems for context-free languages. Mathematical Systems Theory, Vol. 3:1, June 1969, 119-124.

  • An n log n algorithm for minimizing states in a finite automaton. Theory of Machines and Computations, 189-196, ed. by Z. Kohavi and A. Paz, Academic Press, New York, 1971.

  • Efficient algorithms for graph manipulation. Commun. ACM, Vol. 16:6, June 1973, 372-378 (with R. Tarjan).

  • Dividing a graph into triconnected components. SIAM J. Computing, Vol. 2:3, September 1973, 135-158 (with R. Tarjan).

  • An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Computing, Vol. 2:4, December 1973, 225-231 (with R. Karp).

  • Linear time algorithm for isomorphism of planar graphs. Proceedings of 6th Annual ACM Symp. on Theory of Computing, Seattle, Washington (April 30-May 2, 1974) (with J. K. Wong).

  • Efficient planarity testing. J. ACM, Vol. 21:4, October 1974, 549-468 (with R. Tarjan). 

  • On the reachability problem for 5-dimensional vector addition systems. TCS, Vol. 8, 1979, 135-159 (with J. Pansiot). 

  • Efficient detection of intersections among spheres. Intl. J. of Robotics Research, Vol. 2:4, 1983, 77-80 (with J. Schwartz and M. Sharir). 

Honors and Awards
  • 2017 Foreign member Chinese Academy of Sciences

  • 2017 NEC C&C Foundation Award

  • 2017 National Academy of Engineering Simon Ramo Founders Award

  • 2016 China Gold Metal Friendship Award

  • 2016 Microsoft Research Outstanding Collaborator

  • 2011-Honorary professorship Jiao Tong University, Shanghai

  • 2010-Ralph S. Watts 72 Excellence in Teaching Award

  • 2010-Einstein professor Chinese Academy of Sciences

  • 2010-IEEE von Neumann Medal

  • 2010-Recognized by the Societe Mathematique de Tunisie (SMT) for "notable services and outstanding contributions in the application of mathematical theories in theoretical computer science",

  • 2009-Honorary degree, Saint Petersburg State University of Information Technologies, Mechanics & Optics. Saint Petersburg, Russia

  • 2009-Member of the National Academy of Sciences

  • 2005 - IEEE Harry H. Goode Memorial Award

  • 1986 - A. M. Turing Award

© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University

邮箱:jhc@sjtu.edu.cn 电话:021-54740299