Journal of the ACM Bibliography

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998. [BibTeX entry]
Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic

General Terms: Algorithms, Theory

Additional Key Words and Phrases: NP-completeness, optimization, proof verification, randomness

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database