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:
Assignments
Scribe Templates
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.
- Quantum Algorithms for Optimization Problems
- Average sensitivity
- Lower Bounds for Algebraic Circuits
- Fine-grained Complexity
- Asymmteric Traveling Salesman Problem
- Streaming Algorithms for Packing and Covering
- Distributed Algorithms
- Hypergraph Sparsification
- KLS Conjecture
- Cheeger's inequality
- Real Stable Polynomials
- SumOfSquares/LP/SDP Hierarchies
- Geometric Intersection Graphs
- Sublinear time algorithms
- Treewidth
- Dynamic Algorithms for Set Cover
- Random Graphs
- Exact Algorithms
- Additive Combinatorics in TCS
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