# SAS

## Seminar

### Locality from circuit lower bounds

Schweikardt, N (Goethe-Universität Frankfurt)
Friday 30 March 2012, 11:30-12:30

Seminar Room 1, Newton Institute

#### 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 finite 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 FO. In this talk I will show how to use circuit lower bounds for proving that Arb-invariant FO queries are Gaifman-local in the following sense: They 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 query.

#### Video

Available Video Formats