COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Locality from circuit lower bounds

## Locality from circuit lower boundsAdd 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. |
## Other listsStatistical Laboratory International Year of Statistics Public Lectures Office of Scholarly Communication humanitas## Other talksRethinking African Studies: The Wisdom of the Elders Lipschitz Global Optimization Replication or exploration? Sequential design for stochastic simulation experiments Development of a Broadly-Neutralising Vaccine against Blood-Stage P. falciparum Malaria Value generalization during human avoidance learning Roland the Hero |