Helsinki Algorithms Seminar: Parinya Chalermsook "Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques"

Multiplicative Weight Updates for Efficient Algorithms and Data Structures: Some New Results from Old Techniques

Parinya Chalermsook
Aalto University

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.

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.