Apr 25th 16:00

Hankyung Ko (Uppsala University): Coxeter combinatorics of double cosets

Abstract: A Coxeter group is a group W together with a generating set S of reflections satisfying the (Coxeter-)braid relations. This talk concerns parabolic double cosets in a Coxeter group, i.e,. double cosets with respect to subgroups generated by subsets of S. I will discuss how to express them and show the double coset braid relations from a joint work with Ben Elias. If there is time, I will also give an "atomic" description obtained more recently, partially jointly with Ben Elias, Nico Libedinsky, Leonardo Patimo.

May 2nd 16:00

Manuel Bodirsky (TU Dresden): The Complexity of Constraint Satisfaction with Semilinear Constraints

Abstract: The linear program feasibility problem is a well-studied example of a constraint satisfaction problem that can be solved in polynomial time. For some other CSPs over numeric domains, the computational complexity is wide open, such as satisfiability of max-plus systems. In this talk I will give a survey on what is known about the border of polynomial-time tractability and NP-hardness for the large class of CSPs where all the allowed constraints come from some fixed set of semilinear relations, i.e., relations that are definable over the rationals with addition and the order.

May 16th 16:00

Mateusz Skomra (LAAS): Smoothed analysis of deterministic discounted and mean-payoff games

Abstract: Deterministic turn-based discounted and mean-payoff games are fundamental classes of games with an unsettled complexity. They belong to the complexity classes NP and coNP, but are not known to be polynomial-time solvable. Furthermore, they are at the bottom of a hierarchy of complexity classes that stratifies the NP search problems. Despite these properties, the problem of solving turn-based games efficiently has been open for 35 years. Nevertheless, even though we do not know how to solve these games in polynomial time in the worst case, practical experiments suggest that solving random games is easy. More precisely, the policy iteration methods, which can take exponentially many steps in the worst case, converge quickly to the solution when the weights of the game are taken at random. The aim of my talk is to give an explanation of this phenomenon using the framework of "smoothed analysis" introduced by Spielman and Teng to explain the real-world efficiency of the simplex method. We prove that if the weights of a turn-based deterministic game are perturbed by a Gaussian noise, then the resulting randomized problem can be solved efficiently by a variant of a policy iteration method. This talk is based on a joint work with Bruno Loff.

May 30th 16:00

Lilla Tothmeresz (ELTE): TBA

Jun 27th 16:00

Karel Devriendt (MPI-MiS): TBA

Jul 4th 16:00

Eleonore Bach (EPFL): TBA

Jul 11th 16:00

Germain Poullot (Uni Osnabrück): TBA