Login with HarvardKey to view all events.

Forecasting and the complexity of randomized algorithms

This is a past event.

Monday, November 23, 2020 1:45pm to 2:45pm

SEAS Shield

Event Dates

Monday, November 23, 2020 1:45pm to 2:45pm

Virtual Event
Add to calendar

Randomness is a powerful tool in the design of algorithms. By giving algorithms the ability to use random bits and letting them err with some small probability, we can solve many computational problems with remarkable efficiency. However, some the most basic questions about randomized algorithms have proven to be surprisingly challenging, and many of those questions even remain open to this day.

In this talk, we will explore the notion of forecasting algorithms, a slight variant on the usual model of randomized algorithms where the algorithm must generate a confidence score along with its output. We will see how forecasting algorithms allow us to bypass some of the inherent difficulties in the analysis of bounded-error randomized algorithms, and lead to new developments on some of fundamental problems related to the composition conjecture for query complexity and to Yao's minimax lemma.

This talk will cover material from joint work with Shalev Ben-David that can be found at arxiv.org/abs/2002.10802 and arxiv.org/abs/2002.10809.

0 people are interested in this event

User Activity

No recent activity