next up previous contents
Next: About this document Up: Fundamentals of Computing Previous: 5.5 Cryptography.

References

1
On-line bibliographies. http://theory.lcs.mit.edu/~dmjones/hbp.

2
T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. 1990, McGraw-Hill.

3
Donald E. Knuth. The Art of Computer Programming. Vol. 1-3. Addison-Wesley, 3d ed., 1997. Additions to v.2 can be found in http://www-cs-faculty.stanford.edu/~knuth/err2-2e.ps.gz .

4
William Feller. An Introduction to Probability Theory and Its Applications. John Wiley & Sons, 1968.

5
S. Lang. Algebra. 3rd ed. 1993, Addison-Wesley.

6
H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill Book Co., 1967.

7
References for section 1:

8
Ja.M. Barzdin', Ja.Ja. Kalnin's. A Universal Automaton with Variable Structure. Automatic Control and Computing Sciences. 8(2):6-12, 1974.

9
E.R. Berlekamp, J.H. Conway, R.K. Guy. Winning Ways. Section 25. Academic Press, 1982.

10
A.N. Kolmogorov, V.A. Uspenskii. On the Definition of an Algorithm. Uspekhi Mat. Nauk 13:3-28, 1958; AMS Transl. 2nd ser.\ 29:217-245, 1963.

11
A. Schoenhage. Storage Modification Machines. SIAM J. on Computing 9(3):490-508, 1980.

12
Yu. Ofman. A Universal Automaton. Transactions of the Moscow Math. Society, pp.200-215, 1965.

13
Section 2:

14
M. Blum. A machine-independent theory of the complexity of recursive functions. J. ACM 14, 1967.

15
M. Davis, ed. The Undecidable. Hewlett, N.Y. Raven Press, 1965.
(The reprints of the original papers of K.Goedel, A.Turing, A.Church, E.Post and others).

16
Shinichi Ikeno. A 6-symbol 10-state Universal Turing Machine. Proc. Inst. of Elec. Comm. Tokyo, 1958.

17
Joel I. Seiferas, Albert R. Meyer. Characterization of Realizable Space Complexities.
Annals of Pure and Applied Logic 73:171-190, 1995.

18
M.O. Rabin. Speed of computation of functions and classification of recursive sets. Third Convention of Sci.Soc. Israel, 1959, 1-2. Abst.: Bull. of the Research Council of Israel, 8F:69-70, 1959.

19
G.S. Tseitin. Talk: seminar on math. logic, Moscow university, 11/14, 11/21, 1956. Also pp. 44-45 in: S.A. Yanovskaya, Math. Logic and Foundations of Math., Math. in the USSR for 40 Years, 1:13-120, 1959, Moscow, Fizmatgiz, (in Russian).

20
Section 3:

21
J. v.Neumann, O. Morgenstern. Theory of Games and Economic Behavior. Princeton Univ. Press, 1944.

22
L. Stockmeyer, A. Meyer. Word problems requiring exponential time. STOC-1973.

23
Ashok K. Chandra, Dexter C. Kozen, Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981.

24
J.M. Robson. N by N checkers is EXPTIME-complete. SIAM J. Comput 13(2), 1984.

25
J.M. Robson. The complexity of Go. Proc. 1983 IFIP World Computer Congress, p. 413-417.

26
A.S. Fraenkel and D. Lichtenstein. Computing a perfect strategy for chess requires time exponential in n. J. Combin. Theory (Ser. A) 31:199-214. ICALP-1981.

27
Section 4:

28
W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4:177-190, 1970.

29
D.B. Yudin and A.S. Nemirovsky. Informational Complexity and Effective Methods for Solving Convex Extremum Problems. Economica i Mat. Metody 12(2):128-142; transl. MatEcon 13:3-25, 1976.

30
E.M. Luks: Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. FOCS-1980.

31
M.R.Garey, D.S.Johnson. Computers and Intractability. W.H.Freeman & Co. 1979.

32
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.

33
Section 5:

34
M.O.Rabin. Probabilistic Algorithms for Testing Primality. J. Number Theory, 12: 128-138, 1980.

35
G.L.Miller. Riemann's Hypothesis and tests for Primality. J. Comp. Sys. Sci. 13(3):300-317, 1976.

36
R. Solovay, V. Strassen. A fast Monte-Carlo test for primality. SIComp 6:84-85, 1977.

37
R. Karp. Combinatorics, Complexity and Randomness. (Turing Award Lecture) Communication of the ACM, 29(2):98-109, 1986.

38
David S. Johnson. The NP-Completeness Column. J. of Algorithms 5, (1984) 284-299.

39
R. Karp. The probabilistic analysis of some combinatorial search algorithms. Algorithms and Complexity. (J.F.Traub, ed.) Academic Press, NY 1976, pp. 1-19.

40
Y. Gurevich, Average Case Complexity, Internat. Symp. on Information Theory, IEEE, Proc. 1985.

41
A.N.Kolmogorov, V.A.Uspenskii. Algorithms and Randomness. Theoria Veroyatnostey i ee Primeneniya = Theory of Probability and its Applications, 3(32):389-412, 1987.

42
M. Li, P.M.B. Vitanyi. Introduction to Kolmogorov Complexity and its Applications. Springer Verlag, New York, 1993.

43
M. Blum, S. Micali. How to generate Cryptographically Strong Sequences. SIAM J. Comp., 13, 1984.

44
A. C. Yao. Theory and Applications of Trapdoor Functions. FOCS-1982.

45
O.Goldreich, L.Levin. A Hard-Core Predicate for all One-Way Functions. STOC-1989, pp. 25-32.

46
R.Rivest, A.Shamir, L.Adleman. A Method for Obtaining Digital Signature and Public-Key Cryptosystems. Comm. ACM, 21:120-126, 1978.

47
M. Blum, S. Goldwasser. An Efficient Probabilistic Encryption Scheme Hiding All Partial Information. Crypto-1982.

48
M. Rabin. Digitalized Signatures as Intractable as Factorization. MIT/LCS/TR-212, 1979.

49
R.Venkatesan, L.Levin. Random Instances of a Graph Coloring Problem are Hard. STOC-1988.



Leonid Levin
Wed Aug 21 20:35:42 EDT 1996