New answers tagged randomized-algorithms
3
votes
Trying to understand the intuition behind Yao's Minimax Principle
It seems worth it to write up the "game" answer.
You are playing a game where you choose an algorithm $A$ and your opponent chooses an input $I$. You want to minimize $C(I,A)$.
First suppose ...
- 7,052
6
votes
Accepted
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\...
- 431
Top 50 recent answers are included