**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 research interests. 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.
**Sum-of-squares method**- A unifying framework for approximation algorithms?- Sum-of-squares proofs and the quest towards optimal algorithms, by Barak and Steurer.
**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.- Lx=b, by Vishnoi.
**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.