## Locally Checkable Proofs in Distributed Computing

Theory of Computing, Volume 12(19), pp. 1-33, 2016

## Bibliography with links to cited articles

[1]   Miklós Ajtai and Ronald Fagin: Reachability is harder for directed than for undirected finite graphs. J. Symbolic Logic, 55(1):113–150, 1990. Preliminary version in FOCS’88. JSTOR.

[2]   Alon Amit, Nathan Linial, Jiří Matoušek, and Eyal Rozenman: Random lifts of graphs. In Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’01), pp. 883–894. ACM Press, 2001. Abstract based on papers in Combinatorica ’02, Combinatorics, Probability and Computing ’06, Random Struct. Algorithms ’02, and Combinatorica ’05. [ACM:365801]

[3]   Dana Angluin: Local and global properties in networks of processors. In Proc. 12th STOC, pp. 82–93. ACM Press, 1980. [doi:10.1145/800141.804655]

[4]   Matti Åstrand and Jukka Suomela: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In Proc. 22nd Ann. ACM Symp. on Parallelism in Algorithms and Architectures (SPAA’10), pp. 294–302. ACM Press, 2010. [doi:10.1145/1810479.1810533]

[5]    Lowell W. Beineke: Characterizations of derived graphs. J. Combinatorial Theory, 9(2):129–135, 1970. [doi:10.1016/S0021-9800(70)80019-9]

[6]   John A. Bondy and Miklós Simonovits: Cycles of even length in graphs. J. Combin. Theory Ser. B, 16(2):97–105, 1974. [doi:10.1016/0095-8956(74)90052-5]

[7]   Reinhard Diestel: Graph Theory. Springer, Berlin, Germany, 3rd edition, 2005. Official website.

[8]   Paul Erds and Alfréd Rényi: Asymmetric graphs. Acta Mathematica Hungarica, 14(3-4):295–315, 1963. [doi:10.1007/BF01895716]

[9]   Ronald Fagin: Generalized first-order spectra and polynomial-time recognizable sets. In R. M. Karp, editor, Complexity of Computation, volume 7, pp. 43–73. ams, 1974. Available at author’s home page.

[10]   Pierre Fraigniaud: Distributed computational complexities: are you Volvo-addicted or NASCAR-obsessed? In Proc. 29th Ann. ACM Symp. on Principles of Distributed Computing (PODC’10), pp. 171–172. ACM Press, 2010. [doi:10.1145/1835698.1835700]

[11]   Pierre Fraigniaud, Amos Korman, and David Peleg: Local distributed decision. In Proc. 52nd FOCS, pp. 708–717. IEEE Comp. Soc. Press, 2011. To appear in J. ACM. J. ACM version available at author’s home page. [doi:10.1109/FOCS.2011.17]

[12]   Cyril Gavoille and David Peleg: Compact and localized distributed data structures. Distributed Computing, 16(2-3):111–120, 2003. [doi:10.1007/s00446-002-0073-5]

[13]   Mika Göös and Jukka Suomela: Locally checkable proofs. In Proc. 30th Ann. ACM Symp. on Principles of Distributed Computing (PODC’11), pp. 159–168. ACM Press, 2011. [doi:10.1145/1993806.1993829]

[14]   Neil Immerman: Descriptive Complexity. Graduate Texts in Computer Science. Springer, Berlin, Germany, 1999.

[15]   Amos Korman and Shay Kutten: On distributed verification. In Proc. 8th Internat. Conf. on Distributed Computing and Networking (ICDN’06), pp. 100–114. Springer, 2006. [doi:10.1007/11947950_12]

[16]   Amos Korman and Shay Kutten: Distributed verification of minimum spanning trees. Distributed Computing, 20(4):253–266, 2007. Preliminary version in PODC’06. [doi:10.1007/s00446-007-0025-1]

[17]   Amos Korman, Shay Kutten, and Toshimitsu Masuzawa: Fast and compact self stabilizing verification, computation, and fault detection of an MST. In Proc. 24th Ann. ACM Symp. on Principles of Distributed Computing (PODC’05), pp. 311–320, 2011. To appear in Distributed Computing. [doi:10.1145/1993806.1993866]

[18]   Amos Korman, Shay Kutten, and David Peleg: Proof labeling schemes. Distributed Computing, 22(4):215–233, 2010. Preliminary version in PODC’05. [doi:10.1007/s00446-010-0095-3]

[19]   Amos Korman, David Peleg, and Yoav Rodeh: Constructing labeling schemes through universal matrices. Algorithmica, 57(4):641–652, 2010. Preliminary version in ISAAC’06. [doi:10.1007/s00453-008-9226-7]

[20]   Eyal Kushilevitz and Noam Nisan: Communication Complexity. Cambridge Univ. Press, Cambridge, UK, 1997. [ACM:264772]

[21]   Moni Naor and Larry J. Stockmeyer: What can be computed locally? SIAM J. Comput., 24(6):1259–1277, 1995. Preliminary version in STOC’93. [doi:10.1137/S0097539793254571]

[22]   Martin Otto: A note on the number of monadic quantifiers in monadic Σ11. Inform. Process. Lett., 53(6):337–339, 1995. [doi:10.1016/0020-0190(94)00219-O]