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. 
Lieu178 
OrateurJoanna Ochremiak 
Emailhttp://www.labri.fr/~jochremiak/ 
UrlCNRS, LaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index