Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

A New Minimax Theorem for Randomized Algorithms

IEEE via YouTube

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

Reviews

Start your review of A New Minimax Theorem for Randomized Algorithms

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.