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 (2)
| Label | Occurrences |
|---|---|
| Yao’s minimax principle canonical | 2 |
| Yao’s principle | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T11438062 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Yao’s minimax principle Context triple: [Andrew Yao, knownFor, Yao’s minimax principle]
-
A.
Probably Approximately Correct learning (PAC learning)
Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.
-
B.
Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
-
C.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
D.
Papadimitriou: Computational Complexity
"Papadimitriou: Computational Complexity" is a widely used graduate-level textbook that systematically develops the theory of computational complexity, including classes like P and NP and the foundations of NP-completeness.
-
E.
Gale’s theorem on linear inequalities
Gale’s theorem on linear inequalities is a fundamental result in convex geometry and linear programming that characterizes the solvability of systems of linear inequalities via an associated alternative system.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Yao’s minimax principle Target entity description: 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.
-
A.
Probably Approximately Correct learning (PAC learning)
Probably Approximately Correct (PAC) learning is a foundational framework in computational learning theory that formalizes what it means for an algorithm to efficiently learn a concept from examples with high probability and small error.
-
B.
Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
-
C.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
D.
Papadimitriou: Computational Complexity
"Papadimitriou: Computational Complexity" is a widely used graduate-level textbook that systematically develops the theory of computational complexity, including classes like P and NP and the foundations of NP-completeness.
-
E.
Gale’s theorem on linear inequalities
Gale’s theorem on linear inequalities is a fundamental result in convex geometry and linear programming that characterizes the solvability of systems of linear inequalities via an associated alternative system.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
result in computational complexity theory
ⓘ
result in randomized algorithms ⓘ theorem in theoretical computer science ⓘ |
| alsoKnownAs |
Yao’s principle
ⓘ
linked to:
Yao’s minimax principle
|
| 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 ⓘ |
| namedAfter |
Andrew Chi-Chih Yao
ⓘ
linked to:
Andrew Yao
|
| originalContext | lower bounds for randomized decision tree complexity ⓘ |
| originatedBy |
Andrew Chi-Chih Yao
ⓘ
linked to:
Andrew Yao
|
| publishedIn |
journal of the ACM
ⓘ
linked to:
Journal of the ACM
|
| relatedTo |
Las Vegas algorithms
ⓘ
Monte Carlo algorithms ⓘ
linked to:
Monte Carlo method
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 ⓘ probability distributions over inputs ⓘ |
| yearProposed | 1977 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Yao’s minimax principle Description of subject: 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.
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Yao’s minimax principle