Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS seminar by Matthew Anderson On Symmetric Circuits and Fixed-Point Logics

LFCS seminar by Matthew Anderson On Symmetric Circuits and Fixed-Point Logics

— filed under:

Title: On Symmetric Circuits and Fixed-Point Logics Speaker: Matthew Anderson, Cambridge venue: IF 4.31-4.33, 4:00pm, 11/2/2014

What
  • LFCS Seminar
When Feb 11, 2014
from 04:00 PM to 05:00 PM
Where IF 4.31-33
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

fixed-point logic with counting quantifiers.

 

 

This is joint work with Anuj Dawar, which will appear in STACS 2014.

Document Actions