Lovasz Local Lemma
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, F. T. Leighton,
C.-J. Lu, S. B. Rao, and A. Srinivasan. SIAM Journal on Computing, Vol. 31, 626-641, 2001.
Total Coloring With $\Delta + poly(\log\Delta)$ Colors,
Hugh Hind, Michael Molloy, Bruce Reed.
SIAM Journal on Computing, Volume 28, Number 3, pp. 816-821.
Approximate Counting and Rapidly Mixing Markov Chains
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons,
D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan.
Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 717-724, 2003.
Presenter: Anurag Dasgupta
Fast Randomized Algorithms for Distributed Edge Coloring, A. Panconesi and A. Srinivasan,
Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 251-262, 1992.
Presenter: Shuquan Hou
An Efficient Distributed Algorithm for Constructing Small Dominating Sets
with L. Jia and T. Suel.
In Distributed Computing 15:193-205.
A preliminary version appears in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 33-42, August 2001.
Miscellaneous Modeling Papers
M. Jerrum and A. Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989.
Mark Jerrum, Alistair Sinclair, and Eric Vigoda,
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
ECCC Report TR00-079.
Approximate Counting by Dynamic Programming,
STOC 2003, 693--699.
A polylogarithmic approximation algorithm for the group Steiner tree problem.
N. Garg, G. Konjevod, R. Ravi.
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer Science Technical Report 99-1776 (October 1999).
J. Kleinberg. Bursty and Hierarchical Structure in Streams.
Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
M. Adler, E. Halperin, R. Karp, and V.V. Vazirani.
A Stochastic Process on the Hypercube with Applications to Peer-to-Peer Networks.
STOC 2003. 575--584.
Censorship Resistant Peer-To-Peer Content Addressable Networks" by Amos Fiat and Jared Saia. Symposium on Discrete Algorithms 2002.