CSE 290A, Spring 2020: Lec 19, Yao's minimax lemma
C. Seshadhri · 77:25
Yao’s minimax lemma reduces worst-case lower bounds for randomized algorithms to a simpler task: find one hard distribution over inputs that is expensive for every deterministic algorithm. Applied to the experts probl...