Abstract
Boolean circuits that decide properties of relational structures, such as graphs, compute functions that are necessarily invariant to permutations of the elements of the input structures. We develop 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. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This implies that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits. This is joint work with Anuj Dawar.