log in  |  register  |  feedback?  |  help  |  web accessibility
Semi-online algorithms: How to cache for structured sequences?
Friday, November 22, 2019, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
There has been growing recent interest in improving analysis of online algorithms by exploiting extra knowledge about the future. Several new models have been proposed leading to the development of learning-augmented algorithms and semi-online algorithms. In this talk, I'll give a brief overview of recent developments in this area using the ski-rental problem as an illustrative example. In the second half of the talk, I'll introduce a new model for the classical paging problem called interleaved caching that aims to model request sequences in multitasking systems with a shared cache and provide tight upper and lower bounds on the competitive ratio.
This is joint work with Ravi Kumar, Zoya Svitkina, and Erik Vee.

Manish Purohit is a research scientist at Google Research, Mountain View. He obtained his PhD from the University of Maryland, College Park in 2016. He is broadly interested in theoretical computer science with a focus on algorithm design and has worked on related areas such as the interplay between machine learning and online algorithms.

This talk is organized by Ahmed Abdelkader