A New Minimax Theorem for Randomized Algorithms
Offered By: IEEE via YouTube
Course Description
Overview
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.
Syllabus
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!
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube