Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-05-14  11:00-12:00
TitreOn the power of symmetric linear programs 
Résumé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. 
OrateurJoanna Ochremiak 

Aucun document lié à cet événement.

Retour à l'index