On the power of symmetric linear programs

Prelegent(ci)

Joanna Ochremiak

Afiliacja

CNRS, LaBRI, Bordeaux

Termin

20 marca 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---