Course projects
There will be a course project which contributes 50% to the course grade.
The purpose is to acquire a deeper understanding on a specific topic/technique of your own interest.
You are encouraged to pick any theoretically-oriented topic close to your own interest.
The basic requirement is to read papers and write a survey, of course you are most welcome to do original research.
Below are some project ideas, mostly further references to topics relevant to the course.
- Concentration inequalities - More tools and applications for concentration of measure.
- Concentration of measure for the analysis of randomized algorithms, by Dubhashi and Panconesi.
- Hashing - why simple hashing works in practice?
- The power of simple tabulation hashing, by Patrascu and Thorup.
- Why simple hash functions work: exploiting the entropy in a data stream, by Chung, Mitzenmacher, and Vahdan.
- Ball and bins: smaller hash families and faster evaluation, by Celis, Reingold, Segev, Wieder.
- k-wise independence - an important concept with various applications.
- Pairwise independence and derandomization, by Luby and Wigderson.
- Small-bias probability spaces: efficient constructions and applications, by Naor and Naor.
- Probabilstic methods - How to use probabilistic analysis to show the existence of combinatorial objects/algorithms?
- The probabilistic method, by Alon and Spencer.
- Rapidly mixing Markov chains - A general way to sample complicated combinatorial objects.
- Markov chains and mixing time, by Levin, Peres, and Wilmer.
- Sublinear algorithms - Random sampling at its best.
- Data streams: algorithms and applications, by Muthukrishnan.
- Sublinear time algorithms, some links.
- Randomized numerical linear algebra - A useful framework for a large class of problems.
- Sketching as a tool for numerical linear algebra, by Woodruff.
- Iterative rounding - A simple method to analyze linear programming relaxations.
- Iterative methods in combinatorial optimization, by Lau, Ravi, and Singh.
- Multiplicative update method - A useful method with diverse applications.
- Multiplicative weights method: a meta-algorithm and its applications, by Arora, Hazan, and Kale.
- Metric embedding - A beautiful area with elegant results and applications.
- Lectures on discrete geometry (chapter 15), by Matousek.
- Graph partitioning - A central problem in approximation algorithms.
- Expander flows, geometric embedding, and graph partitioning, by Arora, Rao, and Vazirani.
- Semidefinite programming - A powerful approach to design approximation algorithms.
- Approximation algorithms and semidefinite programming, by Gartner and Matousek.
- Spectral algorithms - with applications in clustering and learning.
- Spectral algorithms, by Kannan and Vempala.
- Data science - Algorithms for information age.
- Foundations of data science, by Hopcroft and Kannan.
- Graph sparsification - A beautiful theory with algorithmic applications.
- Spectral sparsification of graphs: theory and algorithms, byBatson, Spielman, Srivastava, Teng.
- Laplacian solvers and their applications - A new paradigm for designing fast algorithms.
- Convex optimization - Will continous optimization take over discrete optimization?
- Convex optimization, by Boyd and Vandenberghe.
- The rubber band method - How to use rubber bands to design algorithms?
- Rubber bands, convex embeddings and graph connectivity, by Linial, Lovász and Wigderson.