|
 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.
| |
AHK
|
Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. Part II: Reducibility, Illinois J. Malh. 21 (1977), 491-567.
|
| |
AHU
|
|
 |
Ba
|
|
| |
BaF
|
Babai, L., Fortnow, L.: Arithmetization: a new method in structural complexity theory, Computational Complexity 1 (1991), to appear. Preliminary version: A characterization of #P by straight line programs of polynomials, Proc. 31th IEEE FOCS (1990), pp. 26-34.
|
| |
BFL
|
Babai, L., Fortnow, L., Lund, C.: Non- Deterministic exponential time has two-prover interactive protocols, Computatzonal Complexity 1 (1991), to appear. Preliminary version in: Proc. 31th IEEE FOCS (1990), pp. 16-25.
|
| |
BeF
|
|
| |
BGKW
|
Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62223]
|
| |
BGW
|
Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62213]
|
| |
Bl
|
Blum, M.: Designing programs to check their work, to appear
|
| |
BK
|
|
| |
BLR
|
M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States
[doi> 10.1145/100216.100225]
|
| |
Ca
|
Cat, J.: PSPACE is provable by two provers in one round, manuscript (1990).
|
| |
Co
|
|
| |
FRS
|
Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols, Proc. 3rd Structure in Complexity Theory Conf. (1988), pp. 156-161.
|
| |
Go
|
Gorenstein, D.: The Enormous Theorem, Scientific American 253:6 (December 1985), 104-115.
|
| |
GMR
|
S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States
[doi> 10.1145/22145.22178]
|
| |
GJ
|
|
| |
Gu
|
Gurevich, Yuri: On Kolmogorov Machines and Related Issues. (The Logic in Computer Science Column). Bulletin of EATCS, 1988.
|
| |
Ka
|
Karo, R. M.: Reducibility among Combinatorial Problems, in" R.E. Miller and J.W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York 1972, pp. 85-103.
|
| |
KU
|
Kolmogorov, A.N., Uspenskil, V.A.: On the Definition of an Algorithm. Uspekhi Mat. Nauk,13 (1958), 3-28; AMS Transl. 2nd ser. 29 (1963), 217- 245.
|
| |
Le
|
Levin, L.A." Universal'nyYe perebornyie zadachi. (Universal search problems: in Russian). Prob. lemy Peredachi Informatsii 9(3):265-266. A corrected English translation appears in an appendix to Trakhtenbrot {Tr}.
|
| |
LG
|
Levin, L.A., G~cs, P.: Causal Nets or What Is a Deterministic Computation? Information and Control, 51 (1982).
|
| |
Li
|
Lipton, R. J.: New directions in testing, manuscript (1989).
|
| |
LFKN
|
Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic Methods for Interactive Proof Systems, Proc. 31th IEEE Syrup. on Foundations of Computer Science (1990), pp. 2-10.
|
| |
MS
|
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
|
| |
Of
|
Ofman, Yu.: A Universal Automaton, Transactions of the Moscow Mathematical Society (1965), 200-215.
|
| |
PW
|
Peterson, W. W., Weldon, E. J., Jr.: Error. correcting Codes, MIT Press, 1972.
|
| |
Sh
|
$hamir, A.: IP=PSPACE, Proe. 31th IEEE FOGS (1990), pp. 11-15.
|
| |
Shg
|
SchSnhage, A.: Storage Modification Machines. SIAM J. on Computing, 9(3):490-508, 1980.
|
| |
Swz
|
|
| |
Si
|
|
| |
Sz
|
Szegedy, M.: Efficient MIP protocol and a stronger condition on clique approximation, in preparatiQn
|
| |
Tr
|
Trakhtenbrot, B.A.: A survey of Russian approaches to Perebor (brute-force search) algorlthm#. Auual# of the Hiatory of Computing, 6 (1984), 384-400.
|
CITED BY 56
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
|
|
|
|
|
|
|
|
|
|
|
|
M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.1