E0 206: Theorist's Toolkit, Fall 2021
- Instructors: Arindam Khan
and Anand Louis
- TAs: Arka Ray
- Time: Tue-Thu 11am-12:30pm, Online (Teams).
This course is intended to equip a student interested in studying theoretical computer science
with some of the fundamental tools commonly used in this area.
The following is a suggestive list of possible
- Probabilistic Methods,
- Information Theory,
- Linear Algebraic Methods,
- Discrete Fourier Analysis,
- Convex Optimization Related Techniques,
- Multiplicative Weight Updates.
The course notes posted here will be scribed by students and will not be proof-read or
checked for accuracy and correctness.
Please use the materials at your own risk!
- Lecture 1 (Anand/Arindam): Introductory Class: Logistics, Basics of Probability. (Scribe)
- Lecture 2-3 (Arindam): Probabilistic Methods (Basics, Expectation Methods). (Scribe)
- First use: Ramsey Number Lower Bound: M-U Thm 6.1, A-S Prop 1.1.1, MIT-YZ Ch 1.1, Jacob Fox's notes.
- Application in Combinatorial Number Theory: Large Sum-free Set: A-S Thm 1.4.1, MIT-YZ Ch 2.2, Ronitt Rubinfeld's notes.
Efficient Algorithm: Paper by Kolountzakis, Also see SJ Ch 24.3.
- Application in Extremal Combinatorics: Erdős-Ko-Rado Theorem: A-S Lemma 1, MIT-YZ Ch 1.4, PB Ch 23. More commentary.
Tim Gowers' lecture,
Survey on Intersecting Families.
- Derandomization: Max-cut: M-U Lem 6.2, Anna Karlin's Notes, Also see Section 3.4.2 in Survey on Derandomization.
- More Expectation Method: Balancing Vectors: A-S Thm 2.4.1, MIT-YZ Ch 2.7, Recent Talk by Nikhil Bansal.
- Lecture 4-5 (Arindam): Probabilistic Methods (Alteration, Second Moment Methods, Concentration Inequalities). (Scribe)
- Alteration (Sample and Modify): Independent Set: A-S Ch 3.2, M-U 6.4, Heng Guo's Notes,
Turáns Theorem: PB Ch 32, equivalence, proof.
- Application in Combinatorial Geometry : Heilbronn's Triangle Problem: A-S Ch 3.3, MIT-YZ Ch 3.2,
Research Problems in Discrete Geometry by Pach-Brass-Moser (contains many such interesting problems).
- Second Moment Method: Random Graphs: A-S Thm 4.4.1, M-U 6.5-6.6, MIT-YZ Ch 4.2-4.4, Book on Random Graphs [Frieze-Karonski].
- Application in Number Theory: Hardy-Ramanujan Theorem: A-S Thm 4.2.1, MIT-YZ Ch 4.5, More info on Erdős-Kac.
- Application in Analysis: Weierstrass Approximation Theorem: MIT-YZ Thm 4.32, Lectures on Approximation by Polynomials.
- Lecture 6-7 (Arindam): Probabilistic Methods (Martingales, Lovász Local Lemma). (Scribe)
- Concentration Inequalities: M-U Ch 4. MIT-YZ Ch 5, UW-TR Ch 2, Also see earlier notes.
Discrepancy: A-S Ch 13.1, MIT-YZ Ch 5.2, Chazelle Book (free), Matousek's Book.
- Martingales: M-U Ch 13, MIT-YZ Ch 8,
Doob Martingales, Stopping Times, Notes by James Lee.
Azuma-Hoeffding and McDiarmid's inequality: McDiarmid's survey, Fan Chung and Linyuan Lee's survey,
Applications: concentration of chromatic number and balls/bins: Notes by Fan Chung.
- Lovász Local Lemma: M-U Ch 6.7, A-S Ch 5, UW-TR Ch 2, MIT-YZ Ch 8.
Proof of general version: Jan Vondrak's Notes,
Application in satisfiability and coloring of hypergraphs: Ronitt Rubinfeld's Notes.
Algorithmic LLL: Srinivasan Talk, Vondrak Talk.
- Lecture 8-9 (Arindam): Information Theory (Basics, Inequalities). (Scribe)
- Basics, Entropy, Relative Entropy, Mutual Information, Inequalities: C-T Ch 2, PrinceMB Lec 1, 2, 3, 4, CMUVG Lec 1, 2, 3,
- Counterfeit coins: Erdos-Renyi paper, Article by Dominguez-Montes, Also see Lec 5 of HvdMS.
- Sorting lower bounds: Section 1.1 in the Survey by Jaikumar Radhakrishnan. (contains many other excellent results and applications)
- KL-divergence: Intuition.
- Lecture 10-11 (Arindam): Information Theory (Applications in counting, Shearer's Lemma, Pinsker's Lemma). (Scribe)
- Application: Bounding the Binomial Tails, Counting Perfect Matchings (Bergman's Theorem): PrinceMB Lec 2, HvdMS Lec 5-6, Radhakrishnan's Paper
- Application: Shearer's Lemma, Intersecting Families of Graphs: PrinceMB Lec 8-9, HvdMS Lec 1, 5, SJ Ch 22,
- Application: Lower bounds for coin tossing, bandits. Slivkins Ch 2, Kleinberg's notes , Madhur Tulsiani's notes.
- Lecture 12-13 (Arindam): Streaming Algorithms (Basics, Finding Majority Element, Hashing, Pairwise Independence). (Scribe)
- Basics, Model, Finding Frequent Elements: Bayer-Moore Majority Voting Algo, Misra Gries Algorithms. AC Lec 0, 1.
- Finding Moments of Data Stream: Flajolet-Martin Algorithm for F0, Hash Fucntions, k-wise independence. AC Lec 2.
- Finding frequent Items by Sketching: Count-Min Sketch. AC Lec 5. MPI 3.4.
- Lecture 14-15 (Arindam): Streaming Algorithms (Counting Distinct Elements, Communication Complexity, Hardness of Streaming). (Scribe)
- AMS Estimator for Fk: Reservoir Sampling, Median of Means trick. AC Lec 6.
- Special Case of F2: AMS sketch, AC Lec 7.
- Approximating Fk: Indyk Algorithm, Stable distributions, AC Lec 8.
- Communication Complexity and connection with Streaming Algorithms. CCT Ch 1.
- Lecture 16-17 (Anand): Linear Algebraic Techniques (SVD, Best-fit Subspace, Low Rank Approximations of Matrices). (Scribe)
- Lecture 18-19 (Anand): Linear Algebraic Techniques (Eigenvalues of Graphs, Expander Graphs). (Scribe)
- Lecture 20-21 (Anand): Linear Algebraic Techniques (Cheeger's inequality). (Scribe)
- Lecture 22-23 (Anand): Discrete Fourier Analysis. (Scribe)
- Based on Chapter 1 of Analysis of Boolean Functions by Ryan O'Donnell.
- Lecture 24-25 (Anand): Multiplicative Weights Update Method. (Scribe)
- Lecture 26-27 (Anand): Convex Optimization. (Scribe)
- Based on "Algorithms for Convex Optimization'' by Nisheeth K. Vishnoi, and "Convex Optimization'' by Boyd and Vandenberghe.
- Lecture 28-29 (Anand): PCP. (Scribe)
Course Drop Deadline without mention: 15th October 2021
Course Drop Deadline with mention: 15th November 2021
Last date for instruction: 24th November 2021
Final: TBA (1st -10h December 2021).
We will be teaching materials from multiple books/sources. Some of them are the following.
- [MIT-YZ] Yufei Zhao. Lecture Notes (The Probabilistic Methods in Combinatorics), MIT, 2019.
- [M-U] Michael Mitzenmacher and Eli Upfal. Probability and computing.
Cambridge university press, 2017.
- [A-S] Noga Alon and Joel Spencer, The probabilistic method, John Wiley & Sons, 2004.
- [UW-TR] Thomas Rothvoss, Lecture Notes (Probabilistic Combinatorics), U Washington, 2019.
- [SJ] Stasys Jukna. Extremal combinatorics: with applications in computer science. Springer, 2011 (Contains many interesting exercises with hints).
- [C-T] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, 2012.
- [PrinceMB] Information Theory in Computer Science (Princeton COS 597D, Fall 2011), Taught by Mark Braverman.
- [HvdMS] Information Theory in Computer Science (Harvard CS 229r, Spring 2019), Taught by Madhu Sudan.
- [CMUVG] Information Theory and its applications in theory of computation (CMU 15-859, Spring 2013), Taught by Venkat Guruswami and Mahdi Cheraghchi.
- [TTIC] Information and Coding Theory (TTIC, Fall 2017), Taught by Madhur Tulsiani.
- [Gal] Three tutorial lectures on entropy and counting, David Galvin, 2014.
- [MPI] Kurt Mehlhorn, Streaming Algorithms, 2014.
- [AC] Amit Chakrabarti, Data Stream Algorithms, 2020.
- [CCT] Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015.
- S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
- [BHK] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science, 2020.
- [KV] Ravindran Kannan, Santosh Vempala. Spectral Algorithms, 2009.
- [BV] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
- [NK] Nisheeth K. Vishnoi. Algorithms for Convex Optimization, 2020.
- [AHK] Sanjeev Arora, Elad Hazan, and Satyen Kale. "The multiplicative weights update method: a meta-algorithm and applications."
Theory of Computing 8.1 (2012): 121-164.
- Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.
- Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, 2003.
- Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, 1998.
- Jonathan S. Golan, The Linear Algebra a Beginning Graduate Student Ought to Know, Springer, 2012.
- Roman Vershynin, High-Dimensional Probability.
- Various surveys and lecture notes.
Similar courses elsewhere:
- CMU, 2020: TCS Toolkit, by Ryan O'Donnel.
- Stanford, 2020: The Modern Algorithmic Toolbox, by Gregory Valiant.
- Georgia Tech, 2019: Theory Toolkit, by Santosh Vempala.
- TTIC, 2019: Mathematical Toolkit, by Madhur Tulsiani.
- CMU, 2016: A Theorist's Toolkit, by Ryan O'Donnel and Venkat Guruswamy.
- Yale, 2015: An Algorithmist's Toolkit, by Sushant Sachdeva.
- MIT, 2007: An Algorithmists's Toolkit, by John Kelner.
- Princeton, 2005: A Theorist's Toolkit, by Sanjeev Arora.
Some More Interesting Resources:
For projects you need to select a project topic from the list given below.
Some reference papers are given below.
You are expected to do a survey of the results and techniques in the topic area.
You can form a group of two students and send the project topic and group details
by 27th August, 2021.
You need to submit the final report by the last_day_of_class.
Finally, you need to make a presentation on the topic sometime in mid-November.
- Quantum Algorithms for Optimization Problems
Lower Bounds for Algebraic Circuits
Asymmteric Traveling Salesman Problem
Streaming Algorithms for Packing and Covering
Real Stable Polynomials
Geometric Intersection Graphs
Sublinear time algorithms
Dynamic Algorithms for Set Cover
Additive Combinatorics in TCS
Intended audience: Graduate students in computer science,
and mathematics with theoretical interests.
Interested undergraduate students with very strong mathematical
Prerequisites: Mathematical maturity and a solid background in math
(elementary combinatorics, graph theory, discrete probability, algebra, calculus)
and theoretical computer science (big-O/Omega/Theta, P/NP, basic fundamental algorithms).
Grading: 45% HW, 25% project, 30% final.
Prepared and Maintained by Arindam Khan