Date: September 13, 2018 [Rescheduled]
Speaker: Parinya Chalermsook (Aalto University)
Meeting place: Exactum C122 (Kumpula)
Abstract: Multiplicative Weight Update (MWU) is a powerful online prediction technique that has been useful in algorithms design in the past decades. In this talk, I will give an overview of my recent efforts to use the MWU-style updates to design (i) near-linear time algorithms for approximate LP solvers with exponential number of constraints and (ii) efficient online binary search trees that are able to achieve new search properties.