Local algorithms for independent sets are half-optimal

B. Bollobás, The independence ratio of regular graphs, Proc. Amer. Math. Soc. 83

1981

Earlier work this paper cites.

B.D. McKay, Independent sets in regular graphs of high girth, Ars Combinatorica 23

1987

Earlier work this paper cites.

A.M. Frieze, On the independence number of random graphs, Discrete Mathematics 81

1990

Earlier work this paper cites.

J. B. Shearer, A note on the independence number of triangle free graphs, II, J. Combin. Theory Ser. B 53

Original

1991

Earlier work this paper cites.

A.M. Frieze and T. Łuczak, On the independence and chromatic numbers of random regular graphs, J. Combin. Theory Ser. B 54

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.

B. Bollobás, Random graphs, 2nd ed., Cambridge University Press, 2001

2001

Earlier work this paper cites.

J. Lauer and N. Wormald, Large independent sets in regular graphs of large girth, J. Combin. Theory Ser. B 97

2007

Earlier work this paper cites.

M. Mezard and A. Montanari, Information, physics and computation, Oxford graduate texts, 2009

2009

Cited alongside, same era.

G. Elek and G. Lippner, Borel oracles. an analytical approach to constant-time algorithms, Proc. Amer. Math. Soc. 138

2010

Cited alongside, same era.

D. Gamarnik and D.A. Goldberg, Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections, Combin. Probab. Comput. 19

2010

Cited alongside, same era.

R. Lyons and F. Nazarov, Perfect matchings as iid factors on non-amenable groups, European J. Combin. 32

2011

Cited alongside, same era.

E. Csóka, Random local algorithms, preprint (2012), arXiv:1202.1565

Original

2012

Cited alongside, same era.

J. Ding, A. Sly, N. Sun, Maximum independent sets in random regular graphs, preprint (2013), arXiv:1310.4787

Original

2013

Later among the works it cites.

C. Hoppen and N. Worlmald, Local algorithms, regular graphs of large girth, and random regular graphs, preprint(2013) arXiv:1308.0266v2

Original

2013

Later among the works it cites.

D. Gamarnik and M. Sudan, Limits of local algorithms over sparse random graphs, Proc. 5th Innovations in Theoretical Computer Science Conf. , ACM (2014) pp. 369–376

2014

Closest in time.

H. Hatami, L. Lovász, and B. Szegedy, Limits of local-global convergent graph sequences, Geom. Funct. Anal. 24

2014

Closest in time.

Á. Backhausz, B. Szegedy, and B. Virág, Ramanujan graphings and correlation decay in local algorithms, Random Struct. Alg. 47

2015