6.856 — Randomized Algorithms

By David R. Karger. 2002

302 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/cf2f5b9272942a882057b1cdcd0d6856f917d5a9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Determinantal probability measures (2002, methodology): “We also present several new avenues for further investigation, involving Hilbert spaces, combinatorics, homology, and group representations, among other areas.”
Limiting the spread of misinformation in social networks (2011, background): “Random walk based algorithms can be further categorized as ones that work for undirected graphs [5, 1] and directed graphs [45, 44].”
Markov Chains and Mixing Times: Second Edition (2017, methodology): “) Mironov (2002) (who was interested in how many steps are needed to do a good job of initializing a standard cryptographic protocol) gives an O(n log n) upper bound, using a variation of Broder’s stopping time for random transpositions. Mossel, Peres, and Sinclair (2004) prove a matching (to within”
Uniform spanning forests (2001, methodology): “, Burton and Pemantle (1993). Kenyon (1997) shows that domino tilings have a strong form of conformal invariance and proves the conformal invariance of certain properties in Kenyon (2000). Nonrigorous conformal field theory was used by Duplantier (1992) and Majumdar (1992) to estimate the rate of es”
Random Walks on Graphs: A Survey (2001, methodology): “) This is proved for graphic matroids (Aldous [2], Broder [15], cf.”
Probability on Trees and Networks (2017, methodology): “A better algorithm than these early ones, especially for probabilists, was introduced by Aldous (1990) and Broder (1989). It says that if you start a simple random walk at any vertex of a finite (connected) graph G and draw every edge it traverses except when it would complete a cycle (i.e., except ”
Limit Distributions and Random Trees Derived from the Birthday Problem with Unequal Probabilities (2000, background): “) a finite state Markov chain [8],[20, §6.”
Markov Chains and Mixing Times (2008, methodology): “The bottleneck ratio Φ% has many names in the literature, including conductance, Cheeger constant , and isoperimetric constant . It is more common to relate Φ% to the spectral gap of a Markov chain. This connection is discussed in Chapter 12. The approach to the lower bound for tmix presented here i”
Rumors in a Network: Who's the Culprit? (2009, methodology): “k f1;2;4;2;1;3ggenerated on the graph G N as indicated by the sequence of arrows (left), and the resulting spanning tree (right). G N, which for most graphs is O(NlogN) and for the worst graphs O(N3) [12]. Once we have generated a tree, we use the tree rumor centrality algorithm to calculate the rum”
Rayleigh processes, real trees, and root growth with re-grafting (2004, unknown): “The Aldous-Broder algorithm [AT89, Bro89 , Ald90] is a tree-valued”
Random Complexes and l^2-Betti Numbers (2008, methodology): “rmonic, matroid. Research partially supported by a Visiting MillerResearch Professorship at the University of Calif., Berkeley (2001), NSF grants DMS-0406017 and DMS-0705518 and Microsoft Research. 1 Broder (1989) and Aldous (1990). It was extended to inﬁnite graphs by Pemantle (1991) in response to”
Cutting down trees with a Markov chainsaw (2011, methodology): “) This fact was independently discovered by Broder [14] and Aldous [2], and the above procedure is commonly called the Aldous–Broder algorithm.”