[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 Σ₁¹. Inform. Process. Lett., 53(6):337–339, 1995. [doi:10.1016/0020-0190(94)00219-O]

[23]   Christos H. Papadimitriou: Computational Complexity. Addison-Wesley Publishing Company, 1994.

[24]   Christos H. Papadimitriou and Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Inc., Mineola, NY, USA, 1998. [ACM:31027]

[25]   David Peleg: Distributed Computing: A Locality-Sensitive Approach. Volume 5 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2000. [ACM:355459]

[26]   Thomas Schwentick: On winning Ehrenfeucht games and monadic NP. Ann. Pure Appl. Logic, 79(1):61–92, 1996. Preliminary version in FOCS’94. [doi:10.1016/0168-0072(95)00030-5]

[27]   Thomas Schwentick and Klaus Barthelmann: Local normal forms for first-order logic with applications to games and automata. Discrete Mathematics and Theoretical Computer Science, 3(3):109–124, 1999. Preliminary version in STACS’98. DMTCS.

[28]   Neil J. A. Sloane: The On-Line Encyclopedia of Integer Sequences, 2010. http://oeis.org.

[29]   Jukka Suomela: Survey of local algorithms. ACM Computing Surveys, 45(2):24, 2013. [doi:10.1145/2431211.2431223]