|
 REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
S. Arora, C. Lund, 1#. Motwani, M. Sudan, and M. Szegedy, Proof Verification and Hardness of Approximation Problems, Proc. 33rd Symposium on Foundations of Computer Science, IE, EE Computer Society Press, Los Alamitos, 1992, pp. 14- 23.
|
| |
2
|
S. Arora and M. Safra, Probabilistic Checking of Proofs, Proc. 33rd Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, 1992, pp. 2-13.
|
 |
3
|
László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States
[doi> 10.1145/103418.103428]
|
| |
4
|
|
| |
5
|
E. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes, US Patent Number 4,633,470. Appears in {10}.
|
| |
6
|
A. Condon, j. Feigenbaum, C. Lund, and P. Shot, Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE- Hard Functions, AT#T Bell Laboratories Technical Memorandum, January 12, 1993.
|
| |
7
|
|
| |
8
|
U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico
[doi> 10.1109/SFCS.1991.185341]
|
| |
9
|
|
| |
10
|
|
| |
11
|
D. S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9 (1974), pp. 256-278.
|
| |
12
|
D. Kozen, Lower bounds for natural proof systems, Proc. 18th Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, 1977, pp. 254-266.
|
| |
13
|
|
| |
14
|
|
| |
15
|
C. Papadimitriou and M. Yannakakis. Optimization, Approximation, and Complexity Classes, J. Comput. System Sci., 43 (1991), pp. 425-440.
|
| |
16
|
|
| |
17
|
T. J. Schaefer, On the Complexity of Some Two-Person Perfect-Information Games, J. Cornput. System Sci., 16 (1978), pp. 185-225.
|
| |
18
|
|
CITED BY 10
|
|
|
|
|
|
|
|
Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
M. V. Marathe , H. B. Hunt, III , R. E. Stearns , V. Radhakrishnan, Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.468-477, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1