Fellows Logic Open Seminar

 Symmetry, Logics, and Circuits

Circuits that decide properties of unordered relational structures, such as graphs, compute functions that are necessarily invariant to permutations of the elements of the input structures. I will discuss families of circuits that are symmetric, that is, circuits whose invariance is witnessed by the automorphisms of the circuit induced by permutations of the input structure, and the logics they capture.  This connection between descriptive and circuit complexity allows the translation of inexpressibility results into lower bounds against circuits.  I'll discuss further connections to Boolean and arithmetic circuit complexity and a number of related open questions.