Locality from Circuit Lower Bounds

Matthew Anderson 1 Dieter Van Melkebeek 1 Nicole Schweikardt 2 Luc Segoufin 3
3 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We study the locality of an extension of first-order logic that captures graph queries computable in AC0 , 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 particular interpretation of the numerical predicates. We refer to such formulas as Arb-invariant first-order. We consider the two standard notions of locality, Gaifman and Hanf locality. Our main result gives a Gaifman locality theorem: An Arb-invariant first-order formula cannot distinguish between two tuples that have the same neighborhood up to distance (log n) c , where n represents the number of elements in the structure and c is a constant depending on the formula. When restricting attention to string structures, we achieve the same quantitative strength for Hanf locality. In both cases we show that our bounds are tight. We also present an application of our results to the study of regular languages. Our proof exploits the close connection between first-order formulas and the complexity class AC0 , and hinges on the tight lower bounds for parity on constant-depth circuits.
Type de document :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2012, 46 (1), pp.43. 〈10.1137/110856873〉
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

Contributeur : Luc Segoufin <>
Soumis le : vendredi 5 juin 2015 - 14:35:17
Dernière modification le : jeudi 7 février 2019 - 17:29:22
Document(s) archivé(s) le : mardi 15 septembre 2015 - 11:35:25


Fichiers produits par l'(les) auteur(s)




Matthew Anderson, Dieter Van Melkebeek, Nicole Schweikardt, Luc Segoufin. Locality from Circuit Lower Bounds. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2012, 46 (1), pp.43. 〈10.1137/110856873〉. 〈hal-01160454〉



Consultations de la notice


Téléchargements de fichiers