| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428171 | Information Processing Letters | 2008 | 4 Pages |
Abstract
Given an unknown tournament over {1,…,n}, we show that the query complexity of the question “Is there a vertex with outdegree n−1?” (known as a Condorcet winner in social choice theory) is exactly 2n−⌊log(n)⌋−2. This stands in stark contrast to the evasiveness of this property in general digraphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
