Fetching the paper…
Reading the bibliography…
Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph.
R. Karp and M. Sipser, Maximum matchings in sparse random graphs , 22nd Annual Symposium on Foundations of Computer Science, 1981, pp. 364–375
1981
Earlier work this paper cites.
B. Bollobas, Random graphs , Academic Press, Inc., 1985
1985
Earlier work this paper cites.
A. Frieze, On the independence number of random graphs , Discrete Mathematics 81
1990
Earlier work this paper cites.
N. Alon and J. Spencer, Probabilistic method , Wiley, 1992
1992
Earlier work this paper cites.
A.M. Frieze and T. Łuczak, On the independence and chromatic numbers of random regular graphs , Journal of Combinatorial Theory, Series B 54
1992
Earlier work this paper cites.
Nathan Linial, Locality in distributed graph algorithms , SIAM J. Comput. 21
1992
Earlier work this paper cites.
S. Janson, T. Łuczak, and A. Rucinski, Random graphs , John Wiley and Sons, Inc., 2000
2000
Earlier work this paper cites.
M. Mézard, T. Mora, and R. Zecchina, Clustering of solutions in the random satisfiability problem , Physical Review Letters 94
2005
Earlier work this paper cites.
2005
Earlier work this paper cites.
L. Lovász and B. Szegedy, Limits of dense graph sequences , Journal of Combinatorial Theory, Series B 96
2006
Cited alongside, same era.
Michal Parnas and Dana Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms , Theor. Comput. Sci. 381
2007
Cited alongside, same era.
Huy N. Nguyen and Krzysztof Onak, Constant-time approximation algorithms via local improvements , FOCS, IEEE Computer Society, 2008, pp. 327–336
2008
Cited alongside, same era.
Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak, Local graph partitions for approximation and testing , FOCS, IEEE Computer Society, 2009, pp. 22–31
2009
Cited alongside, same era.
M. Mezard and A. Montanari, Information, physics and computation , Oxford graduate texts, 2009
2009
Cited alongside, same era.
D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi, On the solution space geometry of random formulas , Random Structures and Algorithms 38
2011
Later among the works it cites.
A. Coja-Oghlan, On belief propagation guided decimation for random k-sat , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 957–966
2011
Later among the works it cites.
A. Coja-Oghlan and C. Efthymiou, On independent sets in random graphs , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 136–144
2011
Later among the works it cites.
R. Lyons and F. Nazarov, Perfect matchings as iid factors on non-amenable groups , European Journal of Combinatorics 32
2011
Later among the works it cites.
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie, Fast local computation algorithms , ICS (Bernard Chazelle, ed.), Tsinghua University Press, 2011, pp. 223–238
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. Bayati, D. Gamarnik, and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs , Annals of Probability, to appear. Conference version in Proc. 42nd Ann. Symposium on the Theory of Computing (STOC) (2010)
2010
Cited alongside, same era.
G. Elek and G. Lippner, Borel oracles. an analytical approach to constant-time algorithms , Proc. Amer. Math. Soc, vol. 138, 2010, pp. 2939–2947
2010
Cited alongside, same era.
M. Talagrand, Mean field models for spin glasses: Volume I: Basic examples , Springer, 2010
2010
Cited alongside, same era.
D. Aldous, Some open problems. http://www.stat.berkeley.edu/ ∼ \sim aldous/ Research/OP/index.html
Cited in the paper.
Cited in the paper.
Cited in the paper.
2011
Later among the works it cites.
C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, and K. Vesztergombi, Convergent graph sequences II: Multiway cuts and statistical physics , Ann. of Math. 176
2012
Later among the works it cites.
2012
Later among the works it cites.