• Time: Monday and Wednesday (04:30 pm - 05:45 pm)
• Location: HAAS G066

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

• Lecture 01: Mathematical Inequalities (08 January, 2018)
  Additional Materials:
  • Mathematical Inequalities using Taylor Series
  • Taylor's theorem with the Lagrange form of the remainder (Gowers's Weblog)
• Lecture 02: Summations and Probability (10 January, 2018)
  
• Lecture 03: Probability Basics (17 January, 2018)
  
• Homework 0 (Not to be submitted) [file 1] [file 2]
  
• Lecture 04: Balls and Bins: Birthday Paradox (22 January, 2018)
  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 05: Balls and Bins: Max-Load (24 January, 2018)
  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)
• Homework 1 (Submission Date: February 07) [file 1] [file 2]
  
• Lecture 06: The Power of 2 Choices (28 January, 2018)
  Additional Materials:
  • Section 1.2 of Ph.D. Thesis (Michael David Mitzenmacher)
  • Section 10.1 of Lecture Notes (James R. Lee)
  • The Power of Two Random Choices: A Survey of Techniques and Results
• Lecture 07: Concentration Bounds (31 January, 2018)
  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 08: Chernoff and Hoeffding Bound + Hypergeometric Distribution (05 February, 2018)
  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 09: Hoeffding Bound Proof (07 February, 2018)
  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 10: Independent Bounded Differences Inequality (12 February, 2018)
  Additional Materials:
  • Chapter 3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 11: Application of the Talagrand Inequality (14 February, 2018)
  Additional Materials:
  • Chapter 4 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Homework 2 (Submission Date: March 05) [file 1] [file 2]
  
• Lecture 12: Martingales and Azuma's Inequality (19 February, 2018)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 13: Martingales and Azuma's Inequality (Few Details) (21 February, 2018)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 14: Examples of Martingales and Azuma's Inequality (26 February, 2018)
  Additional Materials:
  • Chapter 3.3 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 15: Lovász Local Lemma (28 February, 2017)
  Additional Materials:
  • 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 16: Generalized Lovász Local Lemma (05 March, 2018)
  Additional Materials:
  • 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 17: Moser-Tardos Algorithm (07 March, 2018)
  Additional Materials:
  • 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 18: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (19 March, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 19: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (21 March, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Revision (26 March, 2018)
  
• Midterm (28 March, 2018)
  
• Lecture 20: Discrete Fourier Analysis on the Boolean Hypercube (Recall and Basics) (02 April, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 21: Discrete Fourier Analysis on the Boolean Hypercube (Convolution) (04 April, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Homework 3 (Submission Date: April 16) [file 1] [file 2]
  
• Lecture 22: Few Applications (XOR Lemma, Small-bias Masking) (09 April, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 23: Few Applications (BLR Linearity Testing, LHL) (11 April, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Lecture 24: Noise Operator (16 April, 2018)
  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 (18 April, 2018)
  Additional Materials:
  • A Brief Introduction to Fourier Analysis on the Boolean Cube (Ronald de Wolf)
  • Analysis of Boolean Functions (Ryan O'Donnell)
• Homework 4 (Submission Date: TBD [file 1] [file 2]
  
• Revision (23 April, 2018)
  
• Revision (25 April, 2018)
  
• Finals (30 March, 2018)
  G066 (13:00 -- 15:00) [NOTE THE TIME]

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