Complexity Theory

• Agrawal, M., Kayal, N., and Saxena, N. PRIMES is in P. Annals of Mathematics 160, 2 (2004), 781–793.

  Article  MATH  MathSciNet  Google Scholar 

• Aho, A. V., Hopcroft, J. E., and Ullman, J. D. The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

  Google Scholar 

• Aho, A. V., Lam, M., Sethi, R., and Ullman, J. D. Compilers: Principles, Techniques, and Tools, second edition, Addison-Wesley, 2007.

  Google Scholar 

• Arora, S., and Safra, S. Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM 45, 1 (1998), 70–122.

  Article  MATH  MathSciNet  Google Scholar 

• Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. Proof verification and the hardness of approximation problems, Journal of the ACM 45, 3 (1998), 501–555.

  Article  MATH  MathSciNet  Google Scholar 

• Arora, S., and Boaz, B. Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

  Google Scholar 

• Babai, L., Fortnow, L., and Lund, C. Nondeterministic exponential time has two-prover interactive protocols, In Proceedings of the 31 ^st Annual IEEE Symposium on Foundations of Computer Science (1990), pp. 16–25.

  Google Scholar 

• Babai, L., Fortnow, L., Levin, L., and Szegedy, M. Checking computations in polylogarithmic time, In Proceedings of the 23 ^rd Annual ACM Symposium on Theory of Computing (1991), pp. 21–32.

  Google Scholar 

• Cobham, A. The intrinsic computational difficulty of functions. In Proceedings of the International Congress for Logic, Methodology, and Philosophy of Science, Y. Bar-Hillel, Ed., North-Holland, 1964. pp. 24–30.

  Google Scholar 

• Cook, S. A. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Conference on the Theory of Computing (1971), pp. 151–158.

  Google Scholar 

• Dinur, I. The PCP theorem by gap amplification. Journal of the ACM 54, 3 (2007).

  Google Scholar 

• Edmonds, J. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449–467.

  Article  MATH  MathSciNet  Google Scholar 

• Feige, U., Goldwasser, S., Lovasz, L., Safra, S., and Szegedy, M. Interactive proofs and the hardness of approximating cliques, Journal of the ACM 43, 2 (1991), 268–292.

  Article  MathSciNet  Google Scholar 

• Garey, M. R., and Johnson, D. S. Computers and Intractability – A Guide to the Theory of NP-completeness. W. H. Freeman, 1979.

  Google Scholar 

• Goldwasser, S., Micali, S., and Rackoff, C. The knowledge complexity of interactive proof systems. SIAM Journal on Computing (1989), 186–208.

  Google Scholar 

• Hartmanis, J., and Stearns, R. E. On the computational complexity of algorithms. Transactions of the American Mathematical Society 117 (1965), 285–306.

  Article  MATH  MathSciNet  Google Scholar 

• Håstad, J. Some optimal inapproximability results. Journal of the ACM 48, 4 (2001), 105–142.

  Article  Google Scholar 

• Hennie, F. C., and Stearns, R. E. Two tape simulation of multitape Turing machines, Journal of the ACM 13, 4 (1966), 533–546.

  Article  MATH  MathSciNet  Google Scholar 

• Johnson, D. S. Approximation algorithms for combinatorial problems. Journal of Computer and Systems Sciences 9 (1974), 256–278.

  Article  MATH  Google Scholar 

• Karp, R. M. Reducibility among combinatorial problems. In Complexity of Computer Computations (1972), R. E. Miller and J. W. Thatcher, Eds., Plenum Press, pp. 85–103.

  Google Scholar 

• Ladner, R. On the structure of polynomial time reducibility. Journal of the ACM 22, 1 (1975), 155–171.

  Article  MATH  MathSciNet  Google Scholar 

• Levin, L. Universal search problems (in Russian). Problemy Peredachi Informatsii 9, 3 (1973), 115–116.

  MATH  MathSciNet  Google Scholar 

• Papadimitriou, C. H. Computational Complexity. Addison-Wesley, 1994.

  Google Scholar 

• Papadimitriou, C. H., and Yannakakis, M. Optimization, approximation, and complexity classes. Journal of Computer and Systems Sciences 43, 3 (1991), 425–440.

  Article  MATH  MathSciNet  Google Scholar 

• Sipser, M. Introduction to the Theory of Computation, Second Edition. Thomson, 2006.

  MATH  Google Scholar 

• Trevisan, L. Inapproximability of combinatorial optimization problems. University of California, Berkeley, 2004.

  Google Scholar 

• Turing, A. On computable numbers with an application to the Entscheidungsproblem. In Proc. London Mathematical Society 42, pp. 230–265, 1936.

  Article  Google Scholar 

• Vazirani, V. Approximation Algorithms. Springer, 2003.

  Google Scholar 

Download references