Logic, automata, algebra and games Wednesday May 9, 2018, 2PM, 3014 Thomas Colcombet (IRIF) Superpolynomial lower bound for complementing unambiguous automata 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. Logic, automata, algebra and games Wednesday March 14, 2018, 2PM, 4033 Joanna Ochremiak (Université Denis Diderot - Paris 7) Proof complexity, constraint satisfaction and graph isomorphism 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. Logic, automata, algebra and games Wednesday February 14, 2018, 2PM, 4033 Joanna Ocremiak (Université Denis Diderot - Paris 7) Proof complexity, constraint satisfaction and graph isomorphism 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.