[Computational Complexity] Favorite Theorems: The Yao Principle
What is the best a probabilistic algorithm can do for the worst-case input? Perhaps it might be easier to show the limitations of a deterministic algorithm on the average over an adversarially chosen distribution of inputs. Andrew Yao observed these values are one and the same.
Andrew Yao, "Probabilistic Computations: Toward a Unified Measure of Complexity." FOCS 1977
Best to view this result as a zero-sum game. Alice chooses a deterministic algorithm A and Ian chooses an input I. Ian receives t dollars from Alice where t is the "cost" of algorithm A on input I. By applying von Neumann's minimax theorem Ian and Alice have probabilistic equilibrium strategies. That is Ian has a distribution of inputs that achieve an expected cost t no matter what algorithm Alice chooses. Also Alice has a probabilistic algorithm (a randomized choice of deterministic algorithms) that will achieve an expected cost of the same t no matter what input Ian chose.
The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.
The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.
Posted by Lance to Computational Complexity at 10/16/2006 03:26:00 PM