Lectures:    Mon-Wed    11:30 am — 12:50 pm

Instructor:    Ashwin Nayak

Office hours:    Thu  3:30—4:30 pm,    and by appointment

Announcements

1. •Jan. 2: CO 432 is being held with CO 739 this term. While the lectures are common to both courses, students in the undergraduate course will be evaluated differently. Please see Learn for the course webpage for CO 432.
   

2. •Jan 2: The project presentations will be held on Apr. 11 or 12, and the project reports will be due on Apr. 19.

Outline

Although it was originally developed as a mathematical theory of communication, information theory has found a growing number of applications in seemingly unrelated domains. Through this course, we will study basic concepts from information theory, properties of entropic quantities, their operational interpretations, and applications in discrete mathematics and computer science. A tentative list of topics includes:

1. •Shannon entropy, divergence, and mutual information
   

2. •basic properties of entropic quantities
   

3. •Chain Rule, Pinsker Inequality, Data Processing Inequality
   

4. •one-shot and asymptotic compression
   

5. •Noisy Coding Theorem and error-correction codes
   

6. •Bregman theorem, Shearer lemma and applications
   

7. •communication complexity of Set Disjointness
   

8. •applications of error-correction codes
   

9. •Lovasz Local Lemma
   

10. •Bonami-Gross Hypercontractive Inequality
    

11. •compression of interactive protocols
    

12. •efficiency of data structures
    

13. •extended linear programming formulations
    

14. •sample complexity in Learning
    

15. •Parallel Repetition Theorem
    

Prerequisites for the course include knowledge of elementary discrete probability theory and mathematical maturity. Familiarity with discrete mathematics and theoretical computer science will be helpful, but may be substituted by sufficient enthusiasm for these subjects.

Evaluation for graduate students will be based on assignments (60%) and a project (40%). The assignments are intended to supplement the lectures and help the students get a more complete appreciation of the topics covered. The project consists of studying further topics in information theory or one or more research articles related to the course, making a presentation to the class, and writing a report.

Tentative outline of lectures

1. •Introduction to the course. Shannon entropy: definition, interpretation, basic properties; prefix-free codes, Kraft Inequality, Source coding theorem; Asymptotic equipartition theorem
   

2. •Subadditivity, tail bound for the Binomial Distribution; conditional entropy, Chain Rule for entropy; lower bound for Frankl Conjecture; Shearer lemma, counting graph embeddings
   

3. •Relative entropy, interpretations, basic properties; Chernoff-Hoeffding bound; complexity of rejection sampling; Chain Rule, Data Processing Inequality, joint convexity; distinguishing two distributions; Pinsker Inequality
   

4. •Mutual information, interpretation, basic properties; complexity of sampling correlations; Chain Rule, Data Processing Inequality; key size for perfect encryption; Fano inequality; Superadditivity for independent random variables, lower bound for Index function; Pinsker Inequality; Hellinger distance, relationship with l1 distance, basic properties
   

5. •Two party communication protocols, public and private coins; Index, Equality, Set Disjointness; Cut and Paste Lemma;   sqrt(n) / log n  lower bound for Set Disjointness
   

6. •Communication over noisy channels, capacity of a channel, examples of simple channels and their capacity; Idea behind channel coding, joint typicality, Channel coding theorem
   

7. •Error-correction codes, distance of a code, error rate, information rate; Hadamard code, Reed-Solomon code; Efficient encoding and decoding for Reed-Solomon codes; Linear codes, generator matrix, distance, dual code
   

8. •k-wise independence, construction using Reed-Solomon codes, support size; algorithm for E3-Sat; k-wise independence and distance of dual code, almost k-wise independence, general construction using binary codes
   

9. •Protocol for Equality revisited; Self-correction and self-testing of Hadamard code; exponential length PCPs for 3-Sat with a constant number of queries
   

10. •Monotone functions and formulae, monotone formulae for Threshold functions; graph entropy, graph entropy of classes of graphs, properties of graph entropy; min-terms, min-terms of OR and AND of functions, graphs constructed from min-terms; lower bound for Threshold function
    

11. •Lovasz local lemma, Ek-Sat, algorithmic proof for Ek-Sat, analysis using lossless coding
    

12. •Linear programming formulations, polytopes, extensions, the permutahedron, extension complexity; Max-Clique, formulation with the correlation polytope; slack matrix, non-negative rank, Yannakakis Factorization Theorem; facets specified by 0-1 vectors, connection to Set Disjointness; lower bound on non-negative rank via sampling disjoint subsets
    

13. •Quantum information basics: von Neumann entropy, Holevo Theorem, compression of pure states
    

References:        [ pdf ]    for lecture material that is not included in the resources below.

Resources

1. •Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, 2nd. edition, Wiley, 2006.
   

2. •Information Theory and its applications in Theory of Computation, course taught by Venkatesan Guruswami and Mahdi Cheraghchi     [ link ]
   

3. •Communication Complexity, course taught by Prahladh Harsha, Meena Mahajan, and Jaikumar Radhakrishnan     [ link ]
   

4. •Coding Theory, course taught by Elchanan Mossel and Chris Umans    [ link ]
   

5. •Coding Theory, course taught by Venkatesan Guruswami    [ link ]
   

6. •Program on Information Theory, Simons Institute, Berkeley    [ link ]
   

Assignments

Collaboration between classmates on the assignments is allowed, and encouraged if you are stuck. However, you are likely to learn more if you think about the assigned problems independently before you initiate a collaboration. You are expected to write solutions on your own, and name the collaborators and any other sources consulted.

1. •Assignment 1: Out Jan. 26, due Fri., Feb. 9 :    [ pdf ]
   

2. •Assignment 2: Out Mar. 1, due Fri., Mar. 15:   [ pdf ]
   

3. •Assignment 3: Out Mar. 15, due Mon., Apr. 1:     [ pdf ]
   

Projects

The project consists of studying one or more advanced topics or research articles related to the course, making a presentation to the class, and writing a report. The presentations will be scheduled later in the term.

Suggested topics and papers for projects:    [ pdf ]

Instructions: Please prepare the presentation in the style of a 25-minute conference talk. Place the key concepts and results you present in context. In particular, define the problem, describe the motivation behind it, the prior work, state the main result and explain its significance. Finally, present what in your opinion is the main technical or conceptual contribution that enables the result.

In the report (5-10 pages), cover the same topics, but in the style of a tutorial or lecture in your own words. Distill the simplest non-trivial case of the result, and present it in as complete a manner as you can. Illustrate your proofs and explanations with examples where appropriate.

University Policies

Please consult this page for university policies relevant to every course.

Contingency plan

In case public health restrictions prevent in-person classes, lectures will be held live, online. Recordings will be available to those unable to join live online classes. Pointers to resources will be provided to students who are unable to attend in-person lectures due to self-isolation.

Last updated January 2, 2024