A New Minimax Theorem for Randomized Algorithms

Explore a groundbreaking 25-minute IEEE conference talk that presents a novel minimax theorem for randomized algorithms. Delve into the research conducted by Shalev Ben-David and Eric Blais from the University of Waterloo, which builds upon and compares with Yao's minimax principle. Examine the standard minimax theorem, investigate a minimax theorem for ratios, and discover how scoring rules provide a solution to the challenges encountered. Learn about transcript interpretation, attempts using bias, and the application of a special scoring rule in this cutting-edge exploration of algorithmic theory.

Intro
Recall Yao's minimax
Comparison with Yao's minimax
Transcript Interpretation
Standard minimax theorem
A minimax theorem for ratios
Attempt using bias
A special scoring rule
Scoring rules to the rescue!