Locality from Circuit Lower Bounds

Matthew Anderson 1 Dieter van Melkebeek 1 Nicole Schweikardt 2 Luc Segoufin 3
3 DAHU - Verification in databases
CNRS - Centre National de la Recherche Scientifique : UMR8643, Inria Saclay - Ile de France, ENS Cachan - École normale supérieure - Cachan, LSV - Laboratoire Spécification et Vérification [Cachan]
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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [44 references]  Display  Hide  Download

https://hal.inria.fr/hal-01160454
Contributor : Luc Segoufin <>
Submitted on : Friday, June 5, 2015 - 2:35:17 PM
Last modification on : Thursday, April 4, 2019 - 11:30:03 AM
Long-term archiving on : Tuesday, September 15, 2015 - 11:35:25 AM

File

arbinv.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

376

Files downloads

249