You are cordially invited to our next Monday Lecture &
Colloquium on May 6th at 14:15 h & 16:00 h at TU Berlin. Location: Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, May 6th  14:15 h Lecture: Matthias Köppe (University of California) Title: Facets of cutgenerating functionology In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finitedimensional techniques of polyhedral combinatorics are complemented by infinitedimensional methods, the study of cutgenerating functions. I will give an introduction to these methods and will explain their connection tolatticefree convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity. Coffee & Tea Break : Room MA 316  Third Floor [British Reading] Time: Monday, May 6th  16:00 h s.t. Colloquium: Tillmann Miltzow (Universität Utrecht) Title: Smoothed Analysis of the Art Gallery Problem In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation.Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bitcomplexity are typical. Note that describing the guard position is the bottleneck to show NPmembership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ERcomplete problem was analyzed by Smoothed Analysis. This is joint work with
Michael Dobbins and Andreas Holmsen.
