Skip to Main content Skip to Navigation
New interface
Journal articles

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], Inria Saclay - Ile de France
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 metadata

Cited literature [44 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Friday, June 5, 2015 - 2:35:17 PM
Last modification on : Friday, November 18, 2022 - 9:23:03 AM
Long-term archiving on: : Tuesday, September 15, 2015 - 11:35:25 AM


Files produced by the author(s)



Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin. Locality from Circuit Lower Bounds. SIAM Journal on Computing, 2012, 46 (1), pp.43. ⟨10.1137/110856873⟩. ⟨hal-01160454⟩



Record views


Files downloads