LFCS seminar by Matthew Anderson On Symmetric Circuits and FixedPoint Logics
Title: On Symmetric Circuits and FixedPoint Logics Speaker: Matthew Anderson, Cambridge venue: IF 4.314.33, 4:00pm, 11/2/2014
What 


When 
Feb 11, 2014 from 04:00 PM to 05:00 PM 
Where  IF 4.3133 
Add event to calendar 
vCal iCal 
Abstract:
This talk examines queries of relational structures defined by
families of Boolean circuits that are invariant to permutations of
their inputs. In particular, I will focus on circuits that are
symmetric, that is, circuits whose invariance is witnessed by the fact
that each permutation of the input structure induces an automorphism
of the circuit. By developing a general algebraic property of
symmetric circuits I shall demonstrate that the queries definable on
structures by uniform families of symmetric Boolean circuits with
majority gates are exactly those definable in the extension of
fixedpoint logic with counting quantifiers.
This is joint work with Anuj Dawar, which will appear in STACS 2014.