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.

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.