~~NOCACHE~~
/* DO NOT EDIT THIS FILE             */

[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Mercredi 9 mai 2018, 14 heures, 3014\\
**Thomas Colcombet** (IRIF) //Superpolynomial lower bound for complementing unambiguous automata//
<button type="link" size="xs" collapse="b23-3412">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3412" collapsed="true">
<well size="sm">
I will explain the proof of a result of Mikhail Raskin published this year (ICALP 2018) that solves a question open for more than a decade: what is the complexity of complementing an unambiguous automaton. 
The result is that complementing an unambiguous automaton may require a superpolynomial number of states, even if the output automaton is non-deterministic. The opposite fact was conjectured.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Mercredi 14 mars 2018, 14 heures, 4033\\
**Joanna Ochremiak** (Université Denis Diderot - Paris 7) //Proof complexity, constraint satisfaction and graph isomorphism//
<button type="link" size="xs" collapse="b23-3413">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3413" collapsed="true">
<well size="sm">
In this second part of my talk I will discuss the algebraic approach to the constraint satisfaction problem (CSP), a framework which was very recently used to confirm the famous Feder-Vardi CSP dichotomy conjecture. I will also indicate how this approach can be employed to analyse the power of various proof systems for CSPs.
</well>
</collapse>


[[seminaires:laag:index|Logique, automates, algèbre et jeux]]\\
Mercredi 14 février 2018, 14 heures, 4033\\
**Joanna Ocremiak** (Université Denis Diderot - Paris 7) //Proof complexity, constraint satisfaction and graph isomorphism//
<button type="link" size="xs" collapse="b23-3414">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b23-3414" collapsed="true">
<well size="sm">
The goal of my talk will be to present some results on the power of various proof systems for the graph isomorphism problem and the constraint satisfaction problem. In order to do so I will give a short introduction to proof complexity, discuss different relaxations of the graph isomorphism problem and the algebraic approach to the constraint satisfaction problem. No prior knowledge on any of those topics is required.
</well>
</collapse>