Algorithms with Prediction

Explore the intersection of machine learning and algorithm design in this 30-minute lecture by Michael Mitzenmacher from Harvard University. Delve into the concept of algorithms with prediction, starting with a motivating example of search costs and the price of misprediction. Examine main results for standard queues, including known and predicted service times. Discover high-level messages and results for single-bit predictions. Investigate online problems such as caching with predictions and frequency estimation. Learn about Learned Bloom Filters and their improved setups, including partitioned versions. Gain insights into the theoretical framework and experimental results. Conclude with a summary and exploration of related themes like advice and beyond worst-case analysis, leaving you with plenty of questions to ponder.