Theory Resources

CSE Home

About Us

Search

Contact Info

This page is devoted to providing computation and complexity resources to students in 531. Links are provided when they are available. Some of the web sites have restricted access (to U.W. IP addresses).

• Library Resources
  • University of Washington Library
  • INSPEC - Extensive database for computer science, EE, and other science and engineering fields. Restricted access. Can be accessed from a U.W. account.
  • ACM Digital Library
  • MathSciNet - Mathematical Reviews on the Web sponsored by the American Mathematical Society. Restricted access. Can be accessed from a U.W. account.
  • MATH - MATH Database 1931-1999 a service of the European Mathematical Society.
  • U.W. library internet resources for CS (various resources that U.W. pays for us to use)
  • ResearchIndex (web crawler that indexes academic papers)
• Journals
  • Information and Computation
  • Journal of Computer and System Sciences
  • Information Processing Letters
  • SIAM Journal on Computing
  • Journal of the ACM
• Books
  • Garey & Johnson, Computers and Intractability, W.H. Freeman, 1979.
    A discussion on NP-completeness with tips on how to find proofs and what to do about the problems. Also contains a list of about 300 NP-complete (and some PSPACE-complete) problems.
  • Papadimitriou, Christos H, Computational complexity, Addison-Wesley, 1994.
  • Hopcroft, Motwani, and Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, 2000.
• Conference Series on Algorithms
  • ACM Symposium on Theory of Computing (STOC)
  • IEEE Computational Complexity conference (formerly Structure in Complexity Theory)
  • Foundations of Computer Science (FOCS)
  • Symposium on Theoretical Aspects of Computer Science (STACS)
• Other Interesting Sites
  • U.W. page on the Steam-Powered Turing Machine or check the east stairwell in Sieg between the 2nd and 3rd floors or the reception area in Paul G. Allen Center.
  • Turing Machine Simulator - program a Turing machine. (Java applet)
  • An online list of NP-optimization problems (the focus here is on approximation algorithms and complexity classes relating to approximability)
  • Complexity Zoo
  • Lance Fortnow's blog

	Department of Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to ladner]