CSE 687-Algorithmic Information Theory

Algorithmic Information Theory

Meetings MWF 9-10 a.m. in CSE 102

Syllabus. We will try to follow this as much as possible, though we may slightly deviate from it as the course goes on.

Meeting Outlines

Section	Date	Topic(s) covered	Notes (Draft)
Prerequisites	July 26	History	-
	July 28	Naïve Set Theory - Cardinality	Section 1 notes (Last changed: Mon Aug 30 15:34:07 2010)
	July 30
	August 2
	August 4	Basic Computability Theory
	August 6
	August 9
Plain Kolmogorov Complexity	August 11	Definitions, invariance with respect to Universal Turing Machine, upper bound estimate.	Section 2 Notes (Last changed: Tue Sep 7 13:13:54 2010)
	August 13	Uncomputability of Kolmogorov complexity.
	August 16	Uncomputability (contd.), Smoothness, Deficiency
	August 18	Problems with the notion of Plain KC
Self-delimiting Kolmogorov Complexity	August 20	Prefix Codes: Kraft Inequality. partial computable prefix functions	Section 3 notes Last changed: Mon Sep 13 12:37:47 2010
	August 23	Invariance Theorem. subadditivity. Comparison between C and K
	August 25	Coding Theorem, Algorithmic Probability.
	August 27	Coding Theorem, Algorithmic Probability.
	Sep 3	Symmetry of Information
	Sep 6
	Sep 8
Randomness	Sept 13	Deficiency of randomness - Uniform distribution	Section 4 notes Fri Sep 24 12:47:37 2010
	Sept 15	Deficiency of randomness - Uniform distribution
	Sept 17	Martin-Löf test for Weak Law of Large Numbers
	Sept 20	Deficiency of randomness - computable distributions
	Sept 22	Deficiency of randomness - computable distributions
	Sept 24	Infinite random sequences - Martingales
	Sept 27	Infinite random sequences - Martingales
Shannon's Information Theory - Introduction	Sept 27	Independence	Section 5 notes (Last Modified: Tue Nov 9 12:24:07 2010)
	Sept 29	Entropy
	Oct 1	Mutual information, Symmetry of information. Jensen's Inequality.
	Oct 4	Kullback Leibler Divergence, Majorization and Schur concavity.
The Incompressibility Method - Introduction	Oct 6	Introduction, Lower bound for 1-tape Turing machines. [3][4]	Section 6 notes
	Oct 18
	Oct 20	Switching Lemma
	Oct 25
	Oct 27
	Oct 29
	Nov 3
Time bounded KC - selected results	Nov 3	An Oracle such that P^A ≠ NP^A

Homeworks Homework 1
Homework 2

References

Section1

Halmos, P. R. Naïve Set Theory, Undergraduate Texts in Mathematics, Springer, 1954.
Cutland, N. J. Computability: An Introduction to recursive function theory. Cambridge University Press, 1980.

Section 2-4

Doty, D. Personal Communication
Gács, P. Lecture notes on descriptive complexity and randomness. [PDF]
Li, M. and Vitanyi, P. M. B. An Introduction to Kolmogorov Complexity and its applications, 2^nd Edition. Springer, 2002.

Section 5

Cover, T. M. and Thomas, J. A. Elements of Information Theory
Yeung, R. W. A First Course in Information Theory. Kluwer, New York, 2002.
Csiszár, I. and Körner J. Information Theory: Coding Theorems for Discrete Memoryless Systems. 2^nd Edition. Cambridge University Press, 2011.

Section 6

Hennie, F. C. Crossing sequences and off-line turing machine computations, Switching Circuit Theory and Logical Design, 1965. SWCT 1965. Sixth Annual Symposium on, 6-8 Oct. 1965, pages 168 - 172, Ann Arbor, MI, USA. [DOI]
Maas, W. Combinatorial lower bound arguments for deterministic and non-deterministic Turing machines, Transactions of the American Mathematical Society, 292:675-693, 1985.[JSTOR]
Li, M. and Vitányi. Tape versus queues and stacks: The lower bounds. Information and Computation, 78: 56-85, 1988.[DOI]
Laplante, S. A Kolmogorov Complexity Proof of Håstad's Switching Lemma: An Exposition. University of Chicago Technical Report 3/94 TR-94-03. [CiteSeer^X]

Section 7

Hartmanis, J. Generalized Kolmogorov Complexity and the Structure of Feasible Computations. 23^rd Annual Symposium on Foudations of Computer Science 1983 (FOCS 1983) [DOI]