Fall 2016

Extending Symmetric Circuits

Tuesday, November 8th, 2016 4:00 pm4:30 pm

Add to Calendar

Perhaps the most important open question in Finite Model Theory is whether there is a logic that captures polynomial time. At the moment there are two candidate logics for capturing PTIME, Choiceless Polynomial Time (CPT) and Rank Logic. As such, much work is done on understanding how expressive these logics are and in developing potentially useful characterisations. In an attempt to develop such a characterisation, Anderson and Dawar developed the notion of a Symmetric Circuits, circuits with the property that each permutation on the input gates induces an automorphism on the circuit, and showed that these circuits are exactly as expressive as Fixed Point Logic.
In this talk I'll discuss methods of enriching the computational power of Symmetric Circuits. Firstly, I'll talk about extending Symmetric Circuits using gates with different symmetry groups, and how this approach can be used to find a circuit characterisation of Rank Logic. Secondly, I'll discuss a weakening the symmetry requirement inspired by CPT, and how this effects the computational power of the model.