BARC talk by Till Miltzow

Tuesday, 18 June, Till Miltzow, assistant professor, Utrecht, will give a talk "Smoothe Analysis of the Art Gallery Problem" 

Title:
Smoothe Analysis of the Art Gallery Problem

Abstract:
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 bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. 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 ER-complete problem was analyzed by Smoothed Analysis.  
https://www.youtube.com/watch?v=Axs7k-qL2zY  (7 minutes)

Joint work with Michael Dobbins and Andreas Holmsen.

Bio:
Till Miltzow did his PhD with Günter Rote in Berlin working mainly in Computational Geometry. Thereafter, he did a postdoc with Daniel Marx in Budapest to work on Parameterized Complexity. After spending some time in Brussels, he moved to Utrecht, where he received a Veni to work independently.