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 the end of October.
You need to Submit a mid-term progress report by December 15 and the final report by the last_day_of_class.
Finally, you need to make a presentation on the topic sometime in January.
- Algorithmic Lovasz Local Lemma and its applications [Taken by Rishikesh and Aditya S.]
- Sensitivity Conjecture and its applications [Taken by KVN Sreenivas]
- Derandomization [Taken by Jenit]
- Lovett-Meka Algorithm and Discrepancy based Rounding
[Taken by Aditya Vikram]
- Graph Streaming Algorithms
[Taken by Prasanna]
- Cheeger's inequality
- Real Stable Polynomials [Taken by Soumit and Adit]
- SumOfSquares/LP/SDP Hierarchies [Taken by Arka and Rameesh]
- Sublinear time algorithms
- PCP
[Taken by Manjunath and Kumar]
- Sketching [Taken by Deepesh and Prateek]
- Error Correcting Codes [Taken by Prajval and Manish]
- Treewidth
- Multiplicative Weight Updates [Taken by Sruthi and Bhargav]
- Random Graphs
- Streaming Algorithms for Coin Tossing
- Color Coding [Taken by Aditya L.]
- Additive Combinatorics in TCS [Taken by Piyush]
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: 40% HW, 25% Projects, 5% Scribe, 30% Final.
Prepared and Maintained by Arindam Khan