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
Divide and Conquer, Sorting and Searching, and Randomized AlgorithmsStanford University via Coursera Unpredictable? Randomness, Chance and Free Will
National University of Singapore via Coursera Biology Meets Programming: Bioinformatics for Beginners
University of California, San Diego via Coursera Finding Hidden Messages in DNA (Bioinformatics I)
University of California, San Diego via Coursera Algorithms for Big Data
Indian Institute of Technology Madras via Swayam