Back to the root file of my research overview.
References (warning: out of date for decades!)
- [FOCS]
Proceedings of the Annual IEEE Symposium on Foundations of Computer Science.
- [STOC]
Proceedings of the Annual ACM Symposium on Theory of Computing.
- Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, On the
Theory of Average Case Complexity. [STOC] 1989, 204--216.
- L. Blum, M. Blum, M. Shub, A Simple Secure Pseudo-Random Number
Generator, Advances in Cryptology ed. D. Chaum, R.L. Rivest and A.T.
Sherman, Plenum Press, 1983, pp 61-78.
- M.Blum, M.Luby, R.Rubinfeld. Self-testing and Self-correcting programs,
with Applications to Numerical Programs. [STOC] 1990.
- M. Blum, S. Micali, How to generate Cryptographically
Strong Sequences of Pseudo Random Bits, [FOCS] 1982; SIAM J. on Computing,
13:850-864, 1984.
- M. Ben-Or, S. Goldwasser, A. Wigderson. Completeness
Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation.
[STOC] 1988, pp. 1-10.
- S. Cook, The complexity of theorem proving
procedures. [STOC] 1971, pp. 151-158.
- U.Feige, S.Goldwasser L.Lovasz, S.Safra, and M.Szegedy. Approximating
Clique is almost NP-complete. [FOCS] 1991, pp. 2-12.
- P. Gacs, On the Symmetry of Algorithmic Information Soviet Math.
Dokl. 15:1477, 1974.
- Peter Gacs. Reliable computation with cellular automata.
Journal of Computer System Science 32/1:15-78, 1986.
- Yu. Gurevich, S. Shelah, Expected computation time for Hamilton path
problem, SIAM Journal of Computing 16:486-502, 1987.
- Yu. Gurevich, Complete and Incomplete Randomized NP Problems [FOCS] 1987,
111-117.
- Yu. Gurevich, Average Case Completeness. Journal of Computer and
System Sciences, 1988.
- Y. Gurevich, Average Case Complexity.
International Symposium on Information Theory, IEEE, Proc. 1985.
- David S. Johnson, The NP-Completeness Column: An
Ongoing Guide. Journal of Algorithms 5:284-299, 1984.
- R. Karp, Reducibility among combinatorial problems,
Complexity of Computer Computations, (R. Miller, J. Thatcher eds.),
Plenum, NY, 1972, pp. 85-103.
- R. Karp, The probabilistic analysis of some combinatorial search
algorithms, Algorithms and Complexity, (J.F.Traub, ed.) Academic
Press, NY 1976, pp. 1-19.
- R.Karp. Combinatorics, Complexity and Randomness. (Turing Award Lecture).
Communication of the ACM, 1986, 29/2, pp. 98-109.
- Donald E. Knuth. The Art Of Computer
Programming, v.2 Seminumerical Algorithms, 3-d edition, 1997,
Section 3.5.F. This section is new to the 3d edition and so available on
the Web in pp. 10, 29-36 of the file of changes
http://www-cs-faculty.stanford.edu/~knuth/err2-2e.ps.gz
- A.N. Kolmogorov, Three Approaches to the Concept of the Amount of
Information, Probl. Inf. Transm. 1(1), 1965.
- A.N.Kolmogorov. Talk abstract (in Russian).
Usp. Mat. Nauk 1968(2):201.
- A.N.Kolmogorov and V.A.Uspenskii, Algorithms and
Randomness, Theoria Veroyatnostey i ee Primeneniya (Theory of Probability
and its Applications), 3/32, 1987, pp. 389-412.
- M. Li, P.M.B. Vitanyi. Introduction to Kolmogorov Complexity and its
Applications. Springer Verlag, New York, 1993.
- Joel I. Seiferas, Albert R. Meyer. Characterization of
Realizable Space Complexities. Annals of Pure and Applied Logic
73:171-190, 1995.
- C.P. Schnorr Process Complexity and effective random
tests. J.Comp.Sys.Sci 7:376-378, 1973.
- C.P.Schnorr and G. Stumpf. A characterization of
complexity sequences. Zeitschrift fur Mathematische Logik und Grundlagen der
Mathematik 21(1):47--56, 1975.
- R.J. Solomonoff. A Formal Theory of Inductive Inference.
Inf. Contr. 7(1):1-22, 1964.
- Daniel A. Spielman. Computationally Efficient
Error-Correcting Codes and Holographic Proofs. Ph.D dissertation. MIT, 1995.
- B.A.Trakhtenbrot. A Survey of Russian Approaches to
Perebor (Brute-force Search) Algorithms.
Annals of the History of Computing, 6(4):384-400, 1984.
- A. C. Yao, Theory and Applications of Trapdoor
Functions. [FOCS] 1982, pp. 80-91.