Randomness is a remarkably 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, even the most basic questions about randomized algorithms have proven to be remarkably 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 the minimax lemma.
This talk will cover material from joint work with Shalev Ben-David that can be found at https://arxiv.org/abs/2002.10802 and https://arxiv.org/abs/2002.10809.
