Locality from circuit lower bounds

Add to your list(s) Download to your calendar using vCal

• Schweikardt, N (Goethe-Universitt Frankfurt)
• Friday 30 March 2012, 11:30-12:30
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.