Reading group "Proof of the PCP theorem"


Organised by Jakub Opršal.


06.11.2017, 13:15IntroductionJakub Opršal
13.11.2017, 13:15Label CoverJakub Opršal
20.11.2017, 13:15ExpandersMarcello Mamino
27.11.2017, 13:15Expanders, continuedMarcello Mamino
04.12.2017, 13:15Expanders, continued 2Marcello Mamino
11.12.2017, 13:15Expanders, continued 3Marcello Mamino
22.01.2018, 13:15PreprocessingAntoine Mottet
05.02.2018, 13:15Amplification and ReductionCaterina Viola
19.02.2018, 13:15Amplification and Reduction, continuedCaterina Viola
26.02.2018, 13:15Amplification and Reduction, continued 2Caterina Viola
05.03.2018, 13:15TBAJakub Opršal

Reading group "Existential theory of the reals"


Organised by Caterina Viola.


  • Some algebraic and geometric computations in PSPACE. John Canny.
  • The complexity of elementary algebra and geometry. Michael Ben-Or, Dexter Kozen, John Reif.

Reading group "Stochastic Games and Logic"

This reading group focuses on interactions between stochastic games and logic.


  • Meetings happen sometime during the week (not necessarily every week). To get on the mailing list send me an email.
  • Meetings are held at the Institute of Algebra, Willersbau C115.


  • Competitive Markov Decision Processes. Jerzy Filar and Koos Vrieze.
  • The Descriptive Complexity of Parity Games. Anuj Dawar and Erich Grädel.
  • Mean-Payoff Games and the Max-Atom Problem. Albert Atserias and Elitza Maneva.
  • Defining Winning Strategies in Fixed-Point Logics. Felix Canavoi, Erich Grädel, Simon Leßenich, Wied Pakusa.

Last update:
Author: Antoine Mottet