Date: October 11, 2018 16:15–17:00
Place: Konemiehentie 2, Room T4 (Otaniemi)
Speaker: Parinya Chalermsook
Title: Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques
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 properties.