On the power of symmetric linear programs

Speaker(s)

Joanna Ochremiak

Affiliation

CNRS, LaBRI, Bordeaux

Date

March 20, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We consider families of symmetric linear programs (LPs) that decide a property of graphs in the sense that,
 for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property.
We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates.
In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting.
This is joint work with Albert Atserias and Anuj Dawar.

---