E0 206: Theorist's Toolkit, Fall 2021

Instructors: Arindam Khan and Anand Louis

TAs: Arka Ray

Time: Tue-Thu 11am-12:30pm, Online (Teams).

Course Description

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 topics:
• Probabilistic Methods,
• Information Theory,
• Linear Algebraic Methods,
• Discrete Fourier Analysis,
• Convex Optimization Related Techniques,
• Multiplicative Weight Updates.

---

Lectures

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)
  • Slides
  • Handwritten notes
  
  
• Lecture 2-3 (Arindam): Probabilistic Methods (Basics, Expectation Methods). (Scribe)
  Handwritten notes.
  • 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)
  Handwritten notes.
  • 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)
  Handwritten notes.
  • 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)
  Handwritten notes.
  • 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)
  Handwritten notes.
  • 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)
  Handwritten notes.
  • 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 F₀, 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)
  Handwritten notes.
  • AMS Estimator for F_k: Reservoir Sampling, Median of Means trick. AC Lec 6.
  • Special Case of F₂: AMS sketch, AC Lec 7.
  • Approximating F_k: 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)
  Slides.
  • KV Ch 1, BHK Ch 3.
  • Expander survey.
  
  
• Lecture 18-19 (Anand): Linear Algebraic Techniques (Eigenvalues of Graphs, Expander Graphs). (Scribe)
  Slides.
  • Based on following lecture notes by Dan Speilman, Madhur Tulsiani, etc.
  • Mohoney's lecture notes, Ryan Odonell's lecture notes, Spielman's lecture notes,
  • Trevisan's lecture notes: part 1, part 2, part 3, part 4.
  
  
• Lecture 20-21 (Anand): Linear Algebraic Techniques (Cheeger's inequality). (Scribe)
  Slides.
  • Based on following lecture notes by Michael Mahoney, Dan Spielman, Luca Trevisan, etc.
  • Spielman's lecture notes, Madhur's lecture notes, Madhur's lecture notes.
  
  
• Lecture 22-23 (Anand): Discrete Fourier Analysis. (Scribe)
  Slides.
  • Based on Chapter 1 of Analysis of Boolean Functions by Ryan O'Donnell.
  
  
• Lecture 24-25 (Anand): Multiplicative Weights Update Method. (Scribe)
  Slides.
  • Based on lectures notes by Sanjeev Arora, Jonathan Kelner, etc.
  • Kelner's lecture notes: part1, part2, Arora's lecture notes , Anupam Gupta's lecture notes: part1 , part2 , MWU Survey by Arora-Hazan-Kale.
  
  
• Lecture 26-27 (Anand): Convex Optimization. (Scribe)
  Slides.
  • Based on "Algorithms for Convex Optimization'' by Nisheeth K. Vishnoi, and "Convex Optimization'' by Boyd and Vandenberghe.
  
  
• Lecture 28-29 (Anand): PCP. (Scribe)
  Slides.
  • PCP History, " Quanta article on UGC.
  
  



Important Dates:
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).

---

References

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:
• [PB] Proofs from the Book, by Aigner and Ziegler, Springer, 2010.
• Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, by Jiri Matousek.
• REU courses on Linear Algebra and Combinatorics, by László Babai.
• Foundations on Probability, by Terry Tao.
• Information Theory Boot Camp, Simon Institute, UC berkeley.




---

Assignments

• HW 0

---

Scribe Templates

• preamble.tex, lect01.tex
• Overleaf: Learn LaTex
• MIT: Intro to LaTex
• Evan Chen's LaTex hacks
• TikZ package for drawing




---

Project Topics

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.


1. Quantum Algorithms for Optimization Problems
• Computational Geometry Problems .
• Dynamic Program Based Exact Algorithms .


2. Average sensitivity
• Varma-Yoshida Graph Algorithms .
• Peng-Yoshida on Spectral Clustering .


3. Lower Bounds for Algebraic Circuits
• Limaye et al. .


4. Fine-grained Complexity
• Survey .
• Fine-Grained Reductions and Quantum Speedups .


5. Asymmteric Traveling Salesman Problem
• Traub-Vygen .
• Svensson et al. .


6. Streaming Algorithms for Packing and Covering
• Bin Packing .
• Set Cover .
• Knapsack .


7. Distributed Algorithms
• Maximal independent sets .
• Edge coloring .
• Shortest paths .


8. Hypergraph Sparsification
• Bansal-Svensson-Trevisan .
• Kapralov et al. .


9. KLS Conjecture
• Paper by Chen .


10. Cheeger's inequality
• Improved Cheeger's Inequality, Kwok et al..


11. Real Stable Polynomials
• Lecture notes by Shayan Gharan.
• Course by Nikhil Srivastava.


12. SumOfSquares/LP/SDP Hierarchies
• Course by Barak and Steurer.
• Rothvoss Survey.
• CWI Reading Group.


13. Geometric Intersection Graphs
• ETH-Tight Algorithms .
• Stabbing rectangles .
• Set cover .


14. Sublinear time algorithms
• Ronitt Rubinfeld's page.
• Goldreich Book.


15. Treewidth
• O'Donnell's Notes.
• Jeff Erickson's Notes.


16. Dynamic Algorithms for Set Cover
• Gupta et al. .
• Assadi et al. .


17. Random Graphs
• Chromatic Number of Random Graphs.


18. Exact Algorithms
• Bin Packing .
• Subset-sum .


19. Additive Combinatorics in TCS
• Article by Shachar Lovett.
• Article by Luca Trevisan.
• Article by by Khodakhast Bibak.



---

Intended audience: Graduate students in computer science, and mathematics with theoretical interests. Interested undergraduate students with very strong mathematical skills.

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

---