Yao’s minimax principle
E926123
result in computational complexity theory
result in randomized algorithms
theorem in theoretical computer science
Yao’s minimax principle is a fundamental result in computational complexity and randomized algorithms that relates the performance of randomized algorithms to the performance of deterministic algorithms against a worst-case input distribution.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Yao’s minimax principle canonical | 2 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
result in computational complexity theory
ⓘ
result in randomized algorithms ⓘ theorem in theoretical computer science ⓘ |
| alsoKnownAs | Yao’s principle NERFINISHED ⓘ |
| appliesTo |
approximation algorithms
ⓘ
communication complexity ⓘ data structure lower bounds ⓘ online algorithms ⓘ randomized decision tree complexity ⓘ |
| assumes |
finite set of deterministic algorithms
ⓘ
finite set of inputs ⓘ |
| category | theorems about randomized algorithms ⓘ |
| compares |
best deterministic algorithm under a fixed input distribution
ⓘ
worst-case expected cost of randomized algorithms ⓘ |
| concerns |
expected performance of algorithms
ⓘ
worst-case input distributions ⓘ |
| coreIdea | performance of a randomized algorithm on the worst-case input is at least the performance of the best deterministic algorithm against a worst-case input distribution ⓘ |
| field |
algorithm design
ⓘ
computational complexity theory ⓘ probabilistic analysis of algorithms ⓘ randomized algorithms ⓘ theoretical computer science ⓘ |
| formalStatement | the expected cost of the best randomized algorithm on the worst input is at least the expected cost of the best deterministic algorithm against some input distribution ⓘ |
| implies | to prove a lower bound for randomized algorithms it suffices to exhibit a hard input distribution for deterministic algorithms ⓘ |
| influenced | development of lower bound techniques in randomized complexity ⓘ |
| mathematicalBasis | von Neumann’s minimax theorem NERFINISHED ⓘ |
| namedAfter | Andrew Chi-Chih Yao NERFINISHED ⓘ |
| originalContext | lower bounds for randomized decision tree complexity ⓘ |
| originatedBy | Andrew Chi-Chih Yao NERFINISHED ⓘ |
| publishedIn | journal of the ACM NERFINISHED ⓘ |
| relatedTo |
Las Vegas algorithms
NERFINISHED
ⓘ
Monte Carlo algorithms NERFINISHED ⓘ distributional complexity ⓘ randomized complexity classes ⓘ |
| relates |
average-case complexity
ⓘ
deterministic algorithms ⓘ randomized algorithms ⓘ worst-case input distributions ⓘ |
| typeOf | minimax result ⓘ |
| typicalUseCase | constructing a hard distribution over inputs to show randomized lower bounds ⓘ |
| usedFor |
proving lower bounds for randomized algorithms
ⓘ
reducing randomized lower bounds to deterministic lower bounds under distributions ⓘ |
| usesConcept |
expected cost
ⓘ
expected running time ⓘ game theory ⓘ minimax theorem NERFINISHED ⓘ probability distributions over inputs ⓘ |
| yearProposed | 1977 ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.