We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>