Yao's principle

In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms to deterministic (non-random) algorithms. It states that, for certain classes of algorithms, and certain measures of the performance of the algorithms, the following two quantities are equal:

• The optimal performance that can be obtained by a deterministic algorithm on a random input (its average-case complexity), for a probability distribution on inputs chosen to be as hard as possible and for an algorithm chosen to work as well as possible against that distribution
• The optimal performance that can be obtained by a random algorithm on a deterministic input (its expected complexity), for an algorithm chosen to have the best performance on its worst case inputs, and the worst case input to the algorithm

Yao's principle is often used to prove limitations on the performance of randomized algorithms, by finding a probability distribution on inputs that is difficult for deterministic algorithms, and inferring that randomized algorithms have the same limitation on their worst case performance.

This principle is named after Andrew Yao, who first proposed it in a 1977 paper. It is closely related to the minimax theorem in the theory of zero-sum games, and to the duality theory of linear programs.

Formulation

Consider any cost measure $c(A,x)$ of an algorithm $A$ on an input $x$, such as its running time, for which we want to study the expected value over randomized algorithms and random inputs. Consider, also, any finite set ${\mathcal {A}}$ of deterministic algorithms (made finite, for instance, by limiting the algorithms to a specific input size), and a finite set ${\mathcal {X}}$ of inputs to these algorithms. Let ${\mathcal {R}}$ denote the class of randomized algorithms obtained from probability distributions over the deterministic behaviors in ${\mathcal {A}}$, and let ${\mathcal {D}}$ denote the class of probability distributions on inputs in ${\mathcal {X}}$. Then, Yao's principle states that:

$$\max _{D\in {\mathcal {D}}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].$$

Here, $\mathbb {E}$ is notation for the expected value, and $x\sim D$ means that $x$ is a random variable distributed according to $D$. Finiteness of ${\mathcal {A}}$ and ${\mathcal {X}}$ allows ${\mathcal {D}}$ and ${\mathcal {R}}$ to be interpreted as simplices of probability vectors, whose compactness implies that the minima and maxima in these formulas exist.

A weaker form of the same principle, as an inequality rather than an equality, converts any hard input distribution for deterministic algorithms into a lower bound on the cost of all randomized algorithms. If $D\in {\mathcal {D}}$ is any specific choice of a hard input distribution, and $R$ is any specific randomized algorithm in ${\mathcal {R}}$, then $$\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].$$ That is, the best possible deterministic performance against distribution $D$ is a lower bound for the performance of any randomized algorithm $R$ against its worst-case input. One may also observe this weaker version of Yao's principle directly, as $$\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)],$$ by linearity of expectation and the principle that $\min \leq \mathbb {E} \leq \max$ for any distribution. By avoiding maximization and minimization over ${\mathcal {D}}$ and ${\mathcal {R}}$, this version of Yao's principle can apply in some cases where ${\mathcal {X}}$ or ${\mathcal {A}}$ are not finite. However, the version of Yao's principle using an equality rather than an inequality can also be useful when proving lower bounds on randomized algorithms. The equality implies that there is no loss of generality in proving lower bounds in this way: whatever the actual best randomized algorithm might be, there is some input distribution through which a matching lower bound on its complexity can be proven.

Applications and examples

Time complexity

When the cost $c$ denotes the running time of an algorithm, Yao's principle states that the best possible running time of a deterministic algorithm, on a hard input distribution, gives a lower bound for the expected time of any Las Vegas algorithm on its worst-case input. Here, a Las Vegas algorithm is a randomized algorithm whose runtime may vary, but for which the result is always correct. For example, this form of Yao's principle has been used to prove the optimality of certain Monte Carlo tree search algorithms for the exact evaluation of game trees.

Comparisons

The time complexity of comparison-based sorting and selection algorithms is often studied using the number of comparisons between pairs of data elements as a proxy for the total time. For these problems, for any fixed number of elements, an input can be expressed as a permutation and a deterministic algorithm can be expressed as a decision tree, both finite in number as Yao's principle requires. A symmetrization argument identifies the hardest input distributions: they are the random permutations, the distributions on $n$ distinct elements for which all permutations are equally likely. This is because, if any other distribution were hardest, averaging it with all permutations of the same hard distribution would be equally hard, and would produce the distribution for a random permutation. Yao's principle extends lower bounds for the average case number of comparisons made by deterministic algorithms, for random permutations, to the worst case analysis of randomized comparison algorithms.

An example given by Yao is the analysis of algorithms for finding the $k$th largest of a given set of $n$ values, the selection problem. Subsequently to Yao's work, Walter Cunto and Ian Munro showed that, for random permutations, any deterministic algorithm must perform at least $n+\min(k,n-k)-O(1)$ expected comparisons. By Yao's principle, the same number of comparisons must be made by randomized algorithms on their worst-case input. The Floyd–Rivest algorithm comes within $O({\sqrt {n\log n}})$ comparisons of this bound.

Evasiveness of graph properties

Another of the original applications by Yao of his principle was to the evasiveness of graph properties, the number of tests of the adjacency of pairs of vertices needed to determine whether a graph has a given property, when the only access to the graph is through such tests. Richard M. Karp conjectured that every randomized algorithm for every nontrivial monotone graph property (a property that remains true for every subgraph of a graph with the property) requires a quadratic number of tests, but only weaker bounds have been proven.

As Yao stated, for graph properties that are true of the empty graph but false for some other graph on $n$ vertices with only a bounded number $s$ of edges, a randomized algorithm must probe a quadratic number of pairs of vertices. For instance, for the property of being a planar graph, $s=9$ because the 9-edge utility graph is non-planar. More precisely, Yao states that for these properties, at least $\left({\tfrac {1}{2}}-p\right){\tfrac {1}{s}}{\tbinom {n}{2}}$ tests are needed, for every $\varepsilon >0$, for a randomized algorithm to have probability at most $p$ of making a mistake. Yao also used this method to show that quadratically many queries are needed for the properties of containing a given tree or clique as a subgraph, of containing a perfect matching, and of containing a Hamiltonian cycle, for small enough constant error probabilities.

Black-box optimization

In black-box optimization, the problem is to determine the minimum or maximum value of a function, from a given class of functions, accessible only through calls to the function on arguments from some finite domain. In this case, the cost to be optimized is the number of calls. Yao's principle has been described as "the only method available for proving lower bounds for all randomized search heuristics for selected classes of problems". Results that can be proven in this way include the following:

• For Boolean functions on $n$-bit binary strings that test whether the input equals some fixed but unknown string, the optimal expected number of function calls needed to find the unknown string is $2^{n-1}+{\tfrac {1}{2}}$. This can be achieved by a function that tests strings in a random order, and proved optimal by using Yao's principle on an input distribution that chooses a uniformly random function from this class.
• A unimodal function $f$ from $n$-bit binary strings to real numbers is defined by the following property: For each input string $x$, either $f(x)$ is the unique maximum value of $f$, or $x$ can be changed in a single bit to a string $y$ with a larger value. Thus, a local search that changes one bit at a time when this produces a larger value will always eventually find the maximum value. Such a search may take exponentially many steps, but nothing significantly better is possible. For any randomized algorithm that performs $2^{o(n)}$ queries, some function in this class will cause the algorithm to have an exponentially small probability of finding the maximum.

Communication complexity

In communication complexity, an algorithm describes a communication protocol between two or more parties, and its cost may be the number of bits or messages transmitted between the parties. In this case, Yao's principle describes an equality between the average-case complexity of deterministic communication protocols, on an input distribution that is the worst case for the problem, and the expected communication complexity of randomized protocols on their worst-case inputs.

An example described by Avi Wigderson (based on a paper by Manu Viola) is the communication complexity for two parties, each holding $n$-bit input values, to determine which value is larger. For deterministic communication protocols, nothing better than $n$ bits of communication is possible, easily achieved by one party sending their whole input to the other. However, parties with a shared source of randomness and a fixed error probability can exchange 1-bit hash functions of prefixes of the input to perform a noisy binary search for the first position where their inputs differ, achieving $O(\log n)$ bits of communication. This is within a constant factor of optimal, as can be shown via Yao's principle with an input distribution that chooses the position of the first difference uniformly at random, and then chooses random strings for the shared prefix up to that position and the rest of the inputs after that position.

Online algorithms

Yao's principle has also been applied to the competitive ratio of online algorithms. An online algorithm must respond to a sequence of requests, without knowledge of future requests, incurring some cost or profit per request depending on its choices. The competitive ratio is the ratio of its cost or profit to the value that could be achieved achieved by an offline algorithm with access to knowledge of all future requests, for a worst-case request sequence that causes this ratio to be as far from one as possible. Here, one must be careful to formulate the ratio with the algorithm's performance in the numerator and the optimal performance of an offline algorithm in the denominator, so that the cost measure can be formulated as an expected value rather than as the reciprocal of an expected value.

An example given by Borodin & El-Yaniv (2005) concerns page replacement algorithms, which respond to requests for pages of computer memory by using a cache of $k$ pages, for a given parameter $k$. If a request matches a cached page, it costs nothing; otherwise one of the cached pages must be replaced by the requested page, at a cost of one page fault. A difficult distribution of request sequences for this model can be generated by choosing each request uniformly at random from a pool of $k+1$ pages. Any deterministic online algorith has ${\tfrac {n}{k+1}}$ expected page faults, over $n$ requests. Instead, an offline algorithm can divide the request sequence into phases within which only $k$ pages are used, incurring only one fault at the start of a phase to replace the one page that is unused within the phase. As an instance of the coupon collector's problem, the expected requests per phase is $(k+1)H_{k}$, where $H_{k}=1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{k}}$ is the $k$th harmonic number. By renewal theory, the offline algorithm incurs ${\tfrac {n}{(k+1)H_{k}}}+o(n)$ page faults with high probability, so the competitive ratio of any deterministic algorithm against this input distribution is at least $H_{k}$. By Yao's principle, $H_{k}$ also lower bounds the competitive ratio of any randomized page replacement algorithm against a request sequence chosen by an oblivious adversary to be a worst case for the algorithm but without knowledge of the algorithm's random choices.

For online problems in a general class related to the ski rental problem, Seiden has proposed a cookbook method for deriving optimally hard input distributions, based on certain parameters of the problem.

Relation to game theory and linear programming

Yao's principle may be interpreted in game theoretic terms, via a two-player zero-sum game in which one player, Alice, selects a deterministic algorithm, the other player, Bob, selects an input, and the payoff is the cost of the selected algorithm on the selected input. Any randomized algorithm $R$ may be interpreted as a randomized choice among deterministic algorithms, and thus as a mixed strategy for Alice. Similarly, a non-random algorithm may be thought of as a pure strategy for Alice. In any two-player zero-sum game, if one player chooses a mixed strategy, then the other player has an optimal pure strategy against it. By the minimax theorem of John von Neumann, there exists a game value $c$, and mixed strategies for each player, such that the players can guarantee expected value $c$ or better by playing those strategies, and such that the optimal pure strategy against either mixed strategy produces expected value exactly $c$. Thus, the minimax mixed strategy for Alice, set against the best opposing pure strategy for Bob, produces the same expected game value $c$ as the minimax mixed strategy for Bob, set against the best opposing pure strategy for Alice. This equality of expected game values, for the game described above, is Yao's principle in its form as an equality. Yao's 1977 paper, originally formulating Yao's principle, proved it in this way.

The optimal mixed strategy for Alice (a randomized algorithm) and the optimal mixed strategy for Bob (a hard input distribution) may each be computed using a linear program that has one player's probabilities as its variables, with a constraint on the game value for each choice of the other player. The two linear programs obtained in this way for each player are dual linear programs, whose equality is an instance of linear programming duality. However, although linear programs may be solved in polynomial time, the numbers of variables and constraints in these linear programs (numbers of possible algorithms and inputs) are typically too large to list explicitly. Therefore, formulating and solving these programs to find these optimal strategies is often impractical.

Extensions

For Monte Carlo algorithms, algorithms that use a fixed amount of computational resources but that may produce an erroneous result, a form of Yao's principle applies to the probability of an error, the error rate of an algorithm. Choosing the hardest possible input distribution, and the algorithm that achieves the lowest error rate against that distribution, gives the same error rate as choosing an optimal algorithm and its worst case input distribution. However, the hard input distributions found in this way are not robust to changes in the parameters used when applying this principle. If an input distribution requires high complexity to achieve a certain error rate, it may nevertheless have unexpectedly low complexity for a different error rate. Ben-David and Blais show that, for Boolean functions under many natural measures of computational complexity, there exists an input distribution that is simultaneously hard for all error rates.

Variant's of Yao's principle have also been considered for quantum computing. In place of randomized algorithms, one may consider quantum algorithms that have a good probability of computing the correct value for every input (probability at least ${\tfrac {2}{3}}$); this condition together with polynomial time defines the complexity class BQP. It does not make sense to ask for deterministic quantum algorithms, but instead one may consider algorithms that, for a given input distribution, have probability 1 of computing a correct answer, either in a weak sense that the inputs for which this is true have probability $\geq {\tfrac {2}{3}}$, or in a strong sense in which, in addition, the algorithm must have probability 0 or 1 of generating any particular answer on the remaining inputs. For any Boolean function, the minimum complexity of a quantum algorithm that is correct with probability $\geq {\tfrac {2}{3}}$ against its worst-case input is less than or equal to the minimum complexity that can be attained, for a hard input distribution, by the best weak or strong quantum algorithm against that distribution. The weak form of this inequality is within a constant factor of being an equality, but the strong form is not.