Yao's principle

GPTKB entity

Statements (16)
Predicate Object
gptkbp:instanceOf computational complexity principle
gptkbp:alsoKnownAs Yao's minimax principle
gptkbp:appliesTo communication complexity
randomized algorithms
decision tree complexity
gptkbp:formedBy gptkb:Andrew_Yao
https://www.w3.org/2000/01/rdf-schema#label Yao's principle
gptkbp:introducedIn 1977
gptkbp:namedAfter gptkb:Andrew_Yao
gptkbp:publishedIn Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS 1977)
gptkbp:relatedTo gptkb:minimax_theorem
game theory
gptkbp:state The expected cost of the best randomized algorithm on the worst-case input is at least the expected cost of the best deterministic algorithm against a worst-case input distribution.
gptkbp:usedIn lower bound proofs for randomized algorithms
gptkbp:bfsParent gptkb:Frances_Yao
gptkbp:bfsLayer 7