Other Reading

I will unfortunately have to skip many interesting topics. Here are some interesting papers in randomized algorithms.

1. A. Goel, M. Kapralov, and S. Khanna. Perfect matchings in sub-linear time
2. Graph Sparsification:
   • See links for Lecture 27 here.
   • See links for Lectures 8 - 12 here.
3. N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments, JCSS 58 (1): 137–147, 1999.
4. Practical Hashing Schemes
   • A. Broder and M. Mitzenmacher. Network applications of Bloom filters: A survey.
   • Universal Hashing due to Carter and Wegman
5. Linear program rounding:
   • P. Raghavan and C. D. Thompson. (1985) Randomized rounding: A technique for provably good algorithms and algorithmic proofs
6. Random graphs and power laws:
   • P. Erdos and A. Renyi. (1958) On random graphs I Publicationes Mathematicae 6: 290–297.
   • P. Erdos and A. Renyi (1960) The evolution of random graphs Pub. Math Inst Hung Acad Sci 5: 17–61.
   • R. Albert and A. L. Barabasi. Statistical mechanics of complex networks. Reviews of modern physics, 2002.
   • M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions
   • R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal. Stochastic models of the web graph. STOC 2000
7. Dan Spielman. Expander graphs, Error correcting codes, and Expander codes (course notes)
8. Smoothed analysis or "Why is knapsack easy in practice"?
   • R. Beier and B. Vocking. Typical Properties of Winners and Losers in Discrete Optimization. SIAM Journal on Computing, 35(4), 855–881, 2006.
9. SAT Solvers and Thresholds, or "Why is SAT easy in practice"?
   • M. Mezard, G. Parisi, and R. Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems. Science, 297, 812-815, 2002.
   • B. Selman, H. Kautz, and B. Cohen. (1995) Local Search Strategies for Satisfiability Testing
   • V. Chvatal and B. Reed. Mick gets some (the odds are on his side). FOCS 1992
   • D. Achlioptas and C. Moore. The Asymptotic Order of the Random k-SAT Threshold. FOCS 2002