Hemanta K. Maji: CS 59000 - MTK (Spring 2016)

CS 59000: Mathematical Toolkit in Computer Science (Spring 2016)

Schedule:

Time: Tuesday and Thursday (4:30 pm - 5:45 pm)
Location: LWSN B134

Instructor:

Hemanta K. Maji
Office: LWSN 1177
Office Hours: By Appointment

Course Outline and Policy: [html]

Lectures:

Lecture 00: Introduction (12 January, 2016)
Lecture 01: Pigeonhole Principle (12 January, 2016)
Lecture 02: Density of Primes (14 January, 2016)
Additional Materials:
- Chapter 1 of Proofs from THE BOOK
- Chapter 5 of A Computational Introduction to Number Theory and Algebra
- Chapter 9 of Asymptopia
Homework 01 (Due by end of day 28 January, 2016)
Lecture 03: The Power of 2 Choices (19 January, 2016)
Additional Materials:
- Section 1.2 of Ph.D. Thesis (Michael David Mitzenmacher)
- Section 15.1 of Lecture Notes (Alistair Sinclair)
- Section 10.1 of Lecture Notes (James R. Lee)
- The Power of Two Random Choices: A Survey of Techniques and Results
Lecture 04: Balls and Bins: Birthday Paradox and Maximum Load (21 January, 2016)
Additional Materials:
- "Balls into Bins" - A Simple and Tight Analysis
- Lecture Notes (Anupam Gupta)
Lecture 05: Concentration Inequalities (26 January, 2016)
Additional Materials:
- Chapter 1 and 2 of Concentration
- Concentration of Measure for the Analysis of Randomized Algorithms
- Chernoff-Hoeffding Bounds for Applications with Limited Independence
- Concentration inequalities and martingale inequalities - a survey
Lecture 06: Martingale Inequalities and Talagrand Inequality (28 January, 2016)
Additional Materials:
- Chapter 3 and 4 of Concentration
- Concentration inequalities and martingale inequalities - a survey
Lecture 07: Lovász Local Lemma and Moser-Tardos Algorithm (02 February, 2016)
Additional Materials:
- Lecture Notes (Alistair Sinclair)
- A constructive proof of the general Lovász Local Lemma
- Moser and Tardos Meet Lovász
- Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion
Lecture 08: Lovász Local Lemma Examples (04 February, 2016)
Additional Materials:
- Section 22.2 and 22.3.1 of Lecture Notes (Alistair Sinclair)
Homework 02 (Due by end of day 16 February, 2016)
Lecture 09: Spectral Graph Theory (09 February, 2016)
Additional Materials:
- Chapter 1 of Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory (Luca Trevisan)
- Course Website: Spectral Graph Theory (Dan Spielman)
- Lectures on Spectral Graph Theory (Fan R. K. Chung)
Lecture 10: Cheeger's Inequalities, Concentration Bounds for Random Walks on Expander Graphs, and Averaging Samplers (11 February, 2016)
Additional Materials:
- Chapter 2 of Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory (Luca Trevisan)
- A Chernoff bound for random walks on expander graphs
- A Sample of Samplers: A Computational Perspective on Sampling
Lecture 11: Properties of Expanders and Graph Products (16 February, 2016)
Additional Materials:
- Chapter 6.1 and 7 from Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory (Luca Trevisan)
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
Lecture 12: SL = L (18 February, 2016)
Additional Materials:
- Undirected Connectivity in Log-Space
Lecture 13: Information Theory and Counting: Shearer's Lemma (23 February, 2016)
Additional Materials:
- Entropy and Counting (Jaikumar Radhakrishnan)
- Three tutorial lectures on entropy and counting
- Course Website: Information Theory in Computer Science (Madhu Sudan)
- Course Website: Information Theory and its applications in theory of computation (Venkatesan Guruswami and Mahdi Cheraghchi)
- Video: Information Theory in Combinatorics (Shachar Lovett) (Part I) (Part II)
- Video: Information Theory in Computational Complexity (Jaikumar Radhakrishnan and Shachar Lovett) (Part I) (Part II) (Part III) (Part IV)
Lecture 14: Shearer's Lemma: Examples (25 February, 2016)
Additional Materials:
- Entropy and Counting (Jaikumar Radhakrishnan)
- Three tutorial lectures on entropy and counting
Lecture 15: Shearer's Lemma: Examples (01 March, 2016)
Additional Materials:
- Entropy and Counting (Jaikumar Radhakrishnan)
- Three tutorial lectures on entropy and counting
Lecture 16: Introduction to Error-correcting Codes (03 March, 2016)
Additional Materials:
- Course Website: Essential Coding Theory (Madhu Sudan) Fall 2001 Fall 2002 Fall 2004 Spring 2008 Spring 2013
- Course Website: Coding Theory (Venkatesan Guruswami)
  Course Website: Introduction to Coding Theory (Venkatesan Guruswami)
Lecture 17: Perfect Codes and Gilbert-Varshamov Bound (08 March)
Additional Materials:
- Course Website: Coding Theory (Venkatesan Guruswami)
  Course Website: Introduction to Coding Theory (Venkatesan Guruswami)
Lecture 18: Shannon's Channel Coding Theorem (10 March)
Additional Materials:
- Course Website: Coding Theory (Venkatesan Guruswami)
  Course Website: Introduction to Coding Theory (Venkatesan Guruswami)
Homework 03 (Due by end of day 31 March, 2016)
Lecture 19: Fourier Analysis on the Boolean Hypercube (22 March)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Lecture 20: Fourier Analysis on the Boolean Hypercube (24 March)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Exam in Class (29 March, 2016)
Lecture 21: Basic Applications of Fourier Analysis (BLR-Test, List-Decoding Hadamard Codes, Smoothening Functions) (31 March)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Lecture 22: Basic Applications of Fourier Analysis (Extractors and Leftover Hash Lemma) (05 April)
Additional Materials:
- Randomness Extraction: A Survey (David Zuckerman)
- An introduction to Randomness Extractors (Ronen Shaltiel)
- Randomness Extractors (Salil Vadhan)
Lecture 23: Course Revision (07 April)
Lecture 24: Hypercontractivity and Applications (12 April)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Lecture 25: Hypercontractivity and Applications (14 April)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Lecture 26: Influence and KKL Theorem (19 April)
Additional Materials:
- A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
- Analysis of Boolean Functions (Ryan O'Donnell)
Lecture 27: Goldreich-Levin Theorem (21 April)
Additional Materials:
- Lecture 12: Goldreich-Levin (Luca Trevisan)
- Three XOR-Lemmas - An Exposition (Oded Goldreich)
Lecture 28: List Decoding Hadamard Code and Goldreich-Levin Hardcore Predicate (26 April)
Additional Materials:
- Lecture 12: Goldreich-Levin (Luca Trevisan)
- Pseudorandomness and Combinatorial Constructions (Luca Trevisan)
- Three XOR-Lemmas - An Exposition (Oded Goldreich)
Lecture 29: Introduction to PCP Theorem (28 April)
Additional Materials:
- A history of the PCP Theorem
- On Dinur's Proof of the PCP Theorem
- The PCP Theorem and Hardness of Approximation (Venkatesan Guruswami and Ryan O'Donnell)
- Lectures 1 through 9: This contains a complete proof of the PCP Theorem (Venkatesan Guruswami and Ryan O'Donnell)

Useful Materials: Representative Course Material