• Time: Monday, Wednesday, and Friday (10:30 am - 11:30 am)
• Location: LWSN B134

• Hemanta K. Maji
• Office: LWSN 1177
• Office Hours: Monday, Wednesday, and Friday (11:30 am - 12:30 pm) and by Appointment

link

• Hai H. Nguyen (email)
• Office Hours: Friday (05:00 pm - 06:00 pm)
• Location: HAAS G050

• Lecture 01: Mathematical Inequalities (07 January, 2019)
  Additional Materials:
  • Mathematical Inequalities using Taylor Series
  • Taylor's theorem with the Lagrange form of the remainder (Gowers's Weblog)
• Lecture 02: Mathematical Inequalities Examples (09 January, 2019)
  Additional Materials:
  • Mathematical Inequalities using Taylor Series
• Lecture 03: Estimating Summations and Stirling's Approximation (11 January, 2019)
  
• Lecture 04: Probability Basics (14 January, 2019)
  
• Homework 1 [Source Files: file1 file2] (Due Date: 25 January, 2019)
  
• Lecture 05: Balls and Bins Experiment (16 January, 2019)
  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 06: Expected Max-Load and Poisson Approximation Theorem (18 January, 2019)
  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 07: Expected Max-Load and Poisson Approximation Theorem (23 January, 2019)
  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 08: Concentration Bounds: Markov and Chebyshev's Inequality (25 January, 2019)
  Additional Materials:
  • Concentration of Measure for the Analysis of Randomized Algorithms
• Lecture 09: Chernoff Bound (28 January, 2019)
  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 [Source Files: file1 file2] (Due Date: 08 February, 2019)
  
• Lecture 10: Chernoff Bound: Generalizations (01 February, 2019)
  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 11: Chernoff Bound: Usable Forms (04 February, 2019)
  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 12: Hoeffding's Bound (06 February, 2019)
  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 13: Independent Bounded Difference Inequality (08 February, 2019)
  Additional Materials:
  • Chapter 3 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 15: Talagrand Inequality (13 February, 2019)
  Additional Materials:
  • Chapter 4 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 16: Talagrand Inequality Application (15 February, 2019)
  Additional Materials:
  • Chapter 4 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Homework 3 [Source Files: file1 file2] (Due Date: 22 February, 2019)
  
• Lecture 17: Sigma-fields and Martingales (18 February, 2019)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 18: Sigma-fields and Martingales (20 February, 2019)
  
• Lecture 19: Martingale Difference Sequence and Azuma-Hoeffding Inequality (22 February, 2019)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 20: Example Problem: Concentration of the Hypergeometric Distribution (25 February, 2019)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 21: Azuma's Inequality Proof (27 February, 2019)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 22: Concentration Inequalities (Concluding Remarks) (01 March, 2019)
  Additional Materials:
  • Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 23: Lovász Local Lemma (04 March, 2019)
  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 24: Proof of Lovász Local Lemma (06 March, 2019)
  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 25: Generalized Lovász Local Lemma (08 March, 2019)
  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 26: Generalized Lovász Local Lemma (Recall and Completion) (18 March, 2019)
  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 27: Revision (20 March, 2019)
• Lecture 28: Revision (22 March, 2019)
• Homework 4 [Source Files: file1 file2] (Due Date: 24 March, 2019)
  
• Lecture 29: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (25 March, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 30: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (27 March, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 31: Discrete Fourier Analysis on the Boolean Hypercube (Recall and Basics) (29 March, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Homework 5 [Source Files: file1 file2] (Due Date: 10 April, 2019)
  
• Lecture 32: Convolution (01 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 33: BLR Linearity Testing (03 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 34: Tackling Probability Distributions and XOR Lemma (05 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 35: Min-Entropy Extraction via Smal-bias Masking (08 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 36: Left-over Hash Lemma (10 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 37: Noisy Version of a Function (12 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Homework 6 [Source Files: file1 file2] (Due Date: 24 April, 2019)
  
• Lecture 38: Hypercontractivity (15 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)
• Lecture 39: Large Sets fool Large Linear Tests (17 April, 2019)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
  • Analysis of Boolean Functions (Yuval Filmus)

CS 59000 MTK (Spring 2018)
CS 59000 MTK (Spring 2017)
CS 59000 MTK (Spring 2016)