• Time: Tuesday and Thursday (12:00 pm - 01:15 pm)
• Location: LWSN 1106

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

• Hai H. Nguyen (email)
• Office: HAAS G050
• Office Hours: 2 pm - 3 pm every Wednesday

• Lecture 00: Introduction (10 January, 2017)
  
• Lecture 01: Mathematical Basics (Probability and Bound on Summations) (10 January, 2017)
  
• Lecture 02: Mathematical Basics (Inequalities) (12 January, 2017)
  
• Homework 1 (Due in class: 26 January, 2017)
  
• Lecture 03: Balls and Bins (Birthday Paradox, Max-Load) (17 January, 2017)
  Additional Materials:
  • "Balls into Bins" - A Simple and Tight Analysis
  • Lecture Notes (Anupam Gupta)
  • Chapter 5.4 of Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Michael Mitzenmacher and Eli Upfal)
• Lecture 04: The Power of 2 Choices (19 January, 2017)
  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 05: Concentration Bounds (24 January, 2017)
  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: Concentration Bounds (Recall, Applications, Generalizations) (26 January, 2017)
  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
• Homework 2 (Due in class: 23 February, 2017)
  
• Lecture 07: Independent Bounded Differences Inequality (31 January, 2017)
  Additional Materials:
  • Chapter 3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 08: Applications of Talagrand Inequality (02 February, 2017)
  Additional Materials:
  • Chapter 4 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 09: Martingales and Azuma's Inequality (07 February, 2017)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration inequalities and martingale inequalities - a survey
  • Concentration of Measure for the Analysis of Randomized Algorithms
• Revision Class (09 February, 2017)
  
• Revision Class (14 February, 2017)
  
• Lecture 10: Lovász Local Lemma (16 February, 2017)
  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 11: Generalized Lovász Local Lemma (21 February, 2017)
  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 12: Error-correcting Codes: Motivation (23 February, 2017)
  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 13: Reed-Solomon Codes with an Example (28 February, 2017)
  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 14: Linear Codes: Examples and Properties (02 March, 2017)
  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)
• Midterm (07 March, 2017)
• Lecture 15: Perfect Codes and Gilbert-Varshamov Bound (09 March, 2017)
  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)
• Homework 3 (Due in class: 04 April, 2017)
  
• Lecture 16: Shannon's Coding Theorem (An Introduction) (21 March, 2017)
  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: Concatenation Codes (23 March, 2017)
  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)
• Some Applications of Coding Theory in Computational Complexity (Luca Trevisan) (Additional Reading Material)
• Lecture 18: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (28 March)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 19: Simple Applications of Fourier Analysis and Convolution (30 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: Extractors (Small-bias Masking) (04 April)
  Additional Materials:
  • Randomness Extraction: A Survey (David Zuckerman)
  • An introduction to Randomness Extractors (Ronen Shaltiel)
  • Randomness Extractors (Salil Vadhan)
• Lecture 21: Extractors (Leftover Hash Lemma) (06 April)
  Additional Materials:
  • Randomness Extraction: A Survey (David Zuckerman)
  • An introduction to Randomness Extractors (Ronen Shaltiel)
  • Randomness Extractors (Salil Vadhan)
• Homework 4 (Due in class: 25 April, 2017)
  
• Lecture 22: Linearity Testing (11 April)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 23: List Decoding of Hadamard Code: Part 1 (13 April)
  Additional Materials:
  • Lecture 12: Goldreich-Levin (Luca Trevisan)
  • Pseudorandomness and Combinatorial Constructions (Luca Trevisan)
  • Three XOR-Lemmas - An Exposition (Oded Goldreich)
• Lecture 24: Goldreich-Levin Hardcore Predicate (18 April)
  Additional Materials:
  • Goldreich-Levin (Luca Trevisan)
• Lecture 25: List Decoding of Hadamard Code: Part 2 (20 April)
  Additional Materials:
  • Lecture 12: Goldreich-Levin (Luca Trevisan)
  • Pseudorandomness and Combinatorial Constructions (Luca Trevisan)
  • Three XOR-Lemmas - An Exposition (Oded Goldreich)

CS 59000 MTK (Spring 2016)