• Time: Tuesday and Thursday (12:00 pm - 01:15 pm)
• Location: University Hall 117

• Hemanta K. Maji
• Office: LWSN 1177
• Office Hours: Schedule appointment by email

link (4-digit code is available on brightspace)

• Hamidreza Amini Khorasgani (email)

• Lecture 00: Introduction (11 January, 2022)
  
• Lecture 01: Mathematical Inequalities (11 January, 2022)
  Additional Materials:
  • Mathematical Inequalities using Taylor Series
  • Taylor's theorem with the Lagrange form of the remainder (Gowers's Weblog)
• Lecture 02: Estimating Summations and Stirling's Approximation (13 January, 2019)
  Additional Materials:
  • Stirling's Formula
  • Interesting Video on Summations
• Homework 1 [Source Files: file1 file2] (Due Date: 28 January, 2022)
  
• Lecture 03: Probability Basics (18 January, 2022)
  Additional Materials:
  • Text for Preliminaries
• Lecture 04: Concentration Bounds: Markov and Chebyshev's Inequality (20 January, 2022)
  Additional Materials:
  • Concentration of Measure for the Analysis of Randomized Algorithms
• Lecture 05: Chernoff Bound: An Introduction (25 January, 2022)
  
• Lecture 06: Chernoff Bound (27 January, 2022)
  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 07: Chernoff Bound: Usable Forms (01 February, 2022)
  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: Hoeffding's Bound (03 February, 2022)
  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: 21 February, 2022)
  
• Lecture 09: Independent Bounded Difference Inequality (08 February, 2022)
  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 10: Talagrand Inequality and Application (10 February, 2022)
  Additional Materials:
  • Chapter 4 of Concentration
  • Concentration of Measure for the Analysis of Randomized Algorithms
  • Concentration inequalities and martingale inequalities - a survey
• Lecture 11 and 12: Sigma-fields and Martingales (15 and 17 February, 2022)
  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: An Example: Hypergeometric Distribution (22 February, 2022)
  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: Azuma's Inequality: Proof (and Concluding Remarks) (24 February, 2022)
  Additional Materials:
  • 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: 13 March, 2022)
  
• Lecture 15: Discrete Fourier Analysis on the Boolean Hypercube (Introduction) (03 March, 2022)
  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 16: Basic Applications (08 March, 2022)
  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 17: Convolution (10 March, 2022)
  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 4 [Source Files: file1 file2] (Due Date: 03 April, 2022)
  
• Lecture 18: Practice with Fourier Analysis (22 March, 2022)
  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 19: BLR Linearity Testing (24 March, 2022)
  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 20: Tackling Probability Distributions and XOR Lemma (29 March, 2022)
  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 21: Min-Entropy Extraction via Small-bias Masking (31 March, 2022)
  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 22: Left-over Hash Lemma and Bonami-Beckner Noise Operator (05 April, 2022)
  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 23: Hypercontractivity (07 April, 2022)
  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 24: Large Sets fool Large Linear Tests (12 April, 2022)
  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: TBD)
  

• Basics
  • Inequalities: Lagrange form of the Taylor's Remainder Theorem, Jensen's Inequality and consequences
  • Summations/Integrals
  • Stirling's Approximation
  • Probability Basics, Pigeonhole Principle
• Balls and Bins Problems
  • Birthday Bound, Max-Load, Coupon Collectors' Problem, Poisson Approximation Theorem
  • The Power of 2 Choices
  • Bloom Filters
  • Randomized Routing on Networks
• Concentration Inequalities
  • Markov Inequality, Chebyshev Inequality
  • Chernoff-Hoeffding Bound
  • Martingales, Filtration, and Azuma's Inequality
  • Talagrand Inequality
• Probabilistic Techniques
  • Lovász Local Lemma and a few Applications
  • Generalized Lovász Local Lemma
  • Moser-Tardos Algorithm
• Discrete Fourier Analysis
  • Basics
  • BLR Linearity Testing
  • Randomness Extraction and Left-over Hash Lemma
  • Hypercontractivity
  • KKL Theorem
  • Pseudorandomness and Goldreich-Levin Theorem

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