CSE 203A - Projects
An experimental study of minimum-cut algorithms, Chekuri, Goldberg, Karger, Levine and Stein, 1997, SODA
The space complexity of approximating frequency moments, Alon, Matias and Szeged, STOC, 1996
Harvey, N., Algebraic Structures and Algorithms for Matching and Matroid Problems, FOCS '06 Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006.
Byrka, J., Grandoni, F., Rothvoss, T., and Sanita, L, An improved LP-based approximation for steiner tree, STOC '10 Proceedings of the 42nd ACM symposium on Theory of computing, 2010.
Harald Racke, Optimal Hierarchical Decompositions for Congestion Minimization in Networks, STOC '08 Proceedings of the 40th ACM symposium on Theory of computing, 2008.
Ramamohan Paturi, Pavel Pudlak, Michael E. Saks, Francis Zane, An improved exponential-time algorithm for $k$-SAT, Journal of the ACM, Vol. 52, Issue 3, pp 337-364, May 2005.
Timon Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General, FOCS '11 Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, 2011
Marcus Isaksson, Guy Kindler, and Elchanan Mossel, The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem, 2010 IEEE 51st Symposium on Foundations of Computer Science, FOCS 2010.
D. Spielman, S-H Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM, Volume 51, Issue 3, 385-463, May 2004
Andreas Björklund, Determinant Sums for Undirected Hamiltonicity, FOCS '10 Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010.
A. Bjroklund, and T. Husfeldt, The Parity of Directed Hamiltonian Cycles, Foundations of Computer Science (FOCS 2013).
Phillip Gibbons, Distinct-Values Estimation over Data Streams, in Data Stream Management, Editors: Minos Garofalakis, Johannes Gehrke, and Rajeev Rastogi. Springer 2012.
S. Muthukrishnan, Data Streams: Algorithms and Applications, NOW, 2005
N. Vishnoi, Lx=b, NOW 2013.
R. Kannan and S. Vempala, Spectral Algorithms, NOW 2009.
S. Arora and R. Ge, New Tools for Graph Coloring, APPROX/RANDOM 2011, LNCS 6845, pp. 1–12, 2011
Andreas Björklund, Thore Husfeldt, and Mikko Koivisto, Set partitioning via inclusion–exclusion, SIAM J. Comput. Volume 39, Issue 2, (special issue for FOCS 2006), pp. 546-563 (2009)
D. Achlioptas, Random Satisfiability, in Handbook of Satisfiability, Editors: Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsch IOS Press, 2008
D. Kane, N. Jelani, and D. Woodruff, An Optimal Algorithm for the Distinct Elements Problem, ACM Symposium on Principles of Database Systems, 2010
D. Kane, N. Jelani, and D. Woodruff, On the exact space complexity of sketching and streaming small norms, SODA '10 Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
R. Montenegro and P. Tetali, Mathematical Aspects of Mixing Times in Markov Chains, NOW
D. Randall, Rapidly Mixing Markov Chains with Applications in Computer Science and Physics, Computing in Science & Engineering , vol. 8, no. 2, pp. 30–41, March, 2006