Project Ideas

Below are some papers that would be very nice class projects.

Smooth Sensitivity and Sampling in Private Data Analysis by K. Nissim, S. Raskhodnikova and A. Smith (STOC 2007)

Terminal Backup, 3D Matching, and Covering Cubic Graphs by E. Anshelevich and A. Karagiozova (STOC 2007).

Resolving the Complexity of Some Data Privacy Problems by J. Blocki and R. Williams (ICALP 2010).

Simple Deterministic Approximation Algorithms for Counting Matchings by M. Bayati, D. Gamarnik,D. Katz, C. Nair and P. Tetali (STOC 2007).

Fully Homomorphic Encryption over the Integers by M.van Dijk, C. Gentry, S. Halevi and V.Vaikuntanathan (IACR 2010).

Regret Minimization and the Price of Total Anarchy by Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett and Aaron Roth (STOC 2008).

A Learning Theory Approach to Non-Interactive Database Privacy by Avrim Blum, Katrina Ligett and Aaron Roth (STOC 2008).

Evolvability from Learning Algorithms by Vitaly Feldman (STOC 2008).

Delegating Computation: Interactive Proofs for Muggles by Shafi Goldwasser,
Yael Tauman Kalai and Guy N. Rothblum (STOC 2008).

A Constructive Proof of the Lavasz Local Lemma by R. Moser (STOC 2009).

Approximating edit distance in near linear time by A. Andoni and K. Onak (STOC 2009).

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract by Chris Peikert (STOC 2009).

Finding, minimizing, and counting weighted subgraphs by V. Vassilevska and R. Williams (STOC 2009).

Perfect matchings in o(n log n) time in regular bipartite graphs by Ashish Goel, Michael Kapralov and Sanjeev Khanna (STOC 2010).

Public-key cryptography from different assumptions by Benny Applebaum, Boaz Barak and Avi Wigderson (STOC 2010).

Improving exhaustive search implies superpolynomial lower bounds by Ryan Williams (STOC 2010).

Interactive privacy via the median mechanism by Aaron Roth and Tim Roughgarden (STOC 2010).

A full derandomization of schöning's k-SAT algorithm by Robin A. Moser and Dominik Scheder (STOC 2011).

Stability Yields a PTAS for k-Median and k-Means Clustering by Awasthi, P. Blum, A. and Sheffet, O (FOCS 2010).

Helpful Links

· The Wiki for FSM's with lots of neat links.

· Mor Harchol-Balter's notes on applying to grad school in computer science.

· Electronic version of the proceedings of STOC

· Electronic version of the proceedings of FOCS.