BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Locality from circuit lower bounds - Schweikardt\, N (Goethe-Unive
 rsitt Frankfurt)
DTSTART:20120330T103000Z
DTEND:20120330T113000Z
UID:TALK37187@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We study the locality of an extension of first-order logic tha
 t captures graph queries computable in AC0\, i.e.\, by families of polynom
 ial-size constant-depth circuits. The extension considers first-order form
 ulas over finite relational structures which may use arbitrary numerical p
 redicates in such a way that their truth value is independent of the parti
 cular interpretation of the numerical predicates. We refer to such formula
 s as Arb-invariant FO.\nIn 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.\
 n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR