BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 coor
 dinates are a "very rare" phenomenon. We give a theoretical explanation. Ne
 xt 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 perturb
 ations of the worst input. The performance is measured in terms of the magn
 itude \delta of the perturbation and the input size. We consider four diffe
 rent models of perturbation. We show that the expected number of bits to de
 scribe optimal guard positions per guard is logarithmic in the input and th
 e magnitude of the perturbation. This shows from a theoretical perspective 
 that rational guards with small bit-complexity are typical. Note that descr
 ibing the guard position is the bottleneck to show NP-membership. The signi
 ficance of our results is that algebraic methods are not needed to solve th
 e Art Gallery Problem in typical instances. This is the first time an ER-co
 mplete problem was analyzed by Smoothed Analysis.   This is joint work with
  Michael Dobbins and Andreas Holmsen. 
DTSTAMP:20200921T161900
DTSTART:20190506T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
 es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Tillmann Miltzow (Universität Utrecht): Smoothed Analysis of the Ar
 t Gallery Problem
UID:95690649@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190506-C-Miltzow.html
END:VEVENT
END:VCALENDAR