In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture (also known as the Aanderaa–Rosenberg conjecture or the evasiveness conjecture) is a group of related conjectures about the decision tree complexity or query complexity of determining graph properties. The decision tree complexity of determining a graph property is the number of questions of the form "Is there an edge between vertex u and vertex v?" that have to be asked to determine whether a graph has a particular property or not. These questions are called queries, and thus the number of such questions that have to be asked is also called the query complexity of the problem. Examples of graph properties are planarity, bipartiteness, emptyness and the property of containing a clique of size k.

The Aanderaa–Rosenberg conjecture states that you need to ask at least Ω(n²) questions to determine non-trivial monotone graph properties (properties which are not destroyed by the addition of edges). The evasiveness conjecture or the Aanderaa–Karp–Rosenberg states that you need exactly n(n − 1)/2 queries for this. For example, a nontrivial graph property is the property of being empty. A graph is the empty graph if it contains no edges at all. One way to test the property of emptiness is to ask all possible questions of the form "Is there an edge between u and v?" and output "empty" if there are no edges at all. Since there are at most n(n − 1)/2 edges in a graph, we can determine this property with n(n − 1)/2 queries. The Aanderaa–Karp–Rosenberg conjecture essentially states that this is the best possible algorithm not just for testing emptiness, but for all monotone graph properties. Clearly any graph property can be determined after making n(n − 1)/2 queries, since the whole graph is determined at this stage.

Currently the conjecture is partially resolved (the lower bound matches the conjectured lower bound up to a constant) for deterministic query complexity, but there is a large gap between the conjectured lower bound and the best provable lower bound for randomized and quantum query complexity. The original conjecture was about deterministic query complexity (and was later extended to randomized query complexity). Since both conjectures are still not resolved completely, this problem has been open for close to 35 years.

Contents 1 Definitions 2 Query complexity 3 Deterministic query complexity 4 Randomized query complexity 5 Quantum query complexity 6 Further reading 7 References

[edit] Definitions

In the context of this article, all graphs will be simple and undirected, unless stated otherwise. This means that the edges of the graph form a set (and not a multiset) and each edge is a pair of distinct vertices. Informally, a graph property is a property of a graph that is independent of labeling. More formally, a graph property is a mapping from the set of all graphs to {0,1} such that isomorphic graphs are mapped to the same value. For example, the property of containing at least 1 vertex of degree 2 is a graph property, but the property that the first vertex has degree 2 is not, because it depends on the labeling of the graph (in particular, it depends on which vertex is the "first" vertex).

A graph property is called non-trivial if it doesn't assign the same value to all graphs. For instance, the property of being a graph is a trivial property, since all graphs possess this property. On the other hand, the property of being empty is non-trivial, because the empty graph possesses this property, but non-empty graphs do not.

A graph property is said to be monotone if the addition of edges does not destroy the property. Alternately, if a graph possesses a monotone property, then every supergraph of this graph on the same vertex set also possesses it. For instance, the property of being nonplanar is monotone: a supergraph of a nonplanar graph is itself nonplanar. However, the property of being regular is not monotone.

The big Oh notation is often used for query complexity. In short, f(n) is O(g(n)) if for large enough n, f(n) ≤ c g(n) for some positive constant c. Similarly, f(n) is Ω(g(n)) if for large enough n, f(n) ≥ c g(n) for some positive constant c. Finally, f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)).

[edit] Query complexity

The deterministic query complexity of evaluating a function on n bits (x₁, x₂, ... ,x_n) is the number of bits x_i that have to be read in the worst case by a deterministic algorithm to determine the value of the function. For instance, if the function takes value 0 when all bits are 0 and takes value 1 otherwise (this is the OR function), then the deterministic query complexity is exactly n. In the worst case, the first n-1 bits read could all be 0, and the value of the function now depends on the last bit. If an algorithm doesn't read this bit, it might output an incorrect answer. (Such arguments are known as adversary arguments.) The number of bits read are also called the number of queries made to the input. One can imagine that the algorithm asks (or queries) the input for a particular bit and the input responds to this query.

The randomized query complexity of evaluating a function is defined similarly, except the algorithm is allowed to be randomized, i.e., it can flip coins and use the outcome of these coin flips to decide which bits to query. However, the randomized algorithm must still output the correct answer for all inputs: it is not allowed to make errors. Such algorithms are called Las Vegas algorithms, which distinguishes them from Monte Carlo algorithms which are allowed to make some error. Randomized query complexity can also be defined in the Monte Carlo sense, but the Aanderaa–Karp–Rosenberg conjecture is about the Las Vegas query complexity of graph properties.

Quantum query complexity is the natural generalization of randomized query complexity, of course allowing quantum queries and responses. Quantum query complexity can also be defined with respect to Monte Carlo algorithms or Las Vegas algorithms, but it is usually taken to mean Monte Carlo quantum algorithms.

In the context of this conjecture, the function to be evaluated is the graph property, and the input is a string of size n(n − 1)/2, which gives the locations of the edges on an n vertex graph, since a graph can have at most n(n − 1)/2 possible edges. The query complexity of any function is upper bounded by n(n − 1)/2, since the whole input is read after making n(n − 1)/2 queries, thus determining the input graph completely.

[edit] Deterministic query complexity

For deterministic algorithms, Arnold Rosenberg originally conjectured that for all nontrivial graph properties on n vertices, deciding whether a graph possesses this property requires Ω(n²) queries.^[1] The non-triviality condition is clearly required because there are trivial properties like "is this a graph?" which can be answered with no queries at all.

The conjecture was disproved by Aanderaa, who exhibited a directed graph property (the property of containing a "sink") which required only O(n) queries to test. A sink, in a directed graph, is a vertex of indegree n-1 and outdegree 0. This property can be tested with less than 3n queries.^[2] An undirected graph property which can also be tested with O(n) queries is the property of being a scorpion graph, first described in a paper by Best, van Emde Boas and Lenstra.^[2]

Then Aanderaa and Rosenberg formulated a new conjecture (the Aanderaa–Rosenberg conjecture) which says that deciding whether a graph possesses a non-trivial monotone graph property requires Ω(n²) queries.^[3] This conjecture was resolved by Rivest and Vuillemin by showing that at least n²/16 queries are needed to test for any nontrivial monotone graph property.^[4] The bound was further improved to n²/9 by Kleitman and Kwiatkowski,^[5] and then to n²/4 + o(n²) by Jeff Kahn, Michael Saks and Dean Sturtevant.^[6]

Richard Karp conjectured the stronger statement (which is now called the evasiveness conjecture or the Aanderaa–Karp–Rosenberg conjecture) that "every nontrivial monotone graph property for graphs on n vertices is evasive."^[7] A property is called evasive if determining whether a given graph has this property requires exactly n(n − 1)/2 queries.^[8] This conjecture says that the best algorithm for testing any nontrivial monotone property must query all possible edges. This conjecture is still open, although several special graph properties have shown to be evasive for all n. The conjecture has been resolved for the case where n is prime by Jeff Kahn, Michael Saks and Dean Sturtevant using a topological approach.^[6] The conjecture has also been resolved for non-trivial monotone properties on bipartite graphs by Andrew Yao.^[9] Minor-closed properties have also been shown to be evasive for large n.^[10]

[edit] Randomized query complexity

Richard Karp also conjectured that Ω(n²) queries are required for testing nontrivial monotone properties even if randomized algorithms are permitted. No nontrivial monotone property is known which requires less than n²/4 queries to test. A linear lower bound (i.e., Ω(n)) follows from a very general relationship between randomized and deterministic query complexities. The first superlinear lower bound for this problem was given by Andrew Yao who showed that Ω(n log^1/12 n) queries are required.^[11] This was further improved by Valerie King to Ω(n^5/4),^[12] and then by Péter Hajnal to Ω(n^4/3).^[13] This was subsequently improved to the current best known lower bound of Ω(n^4/3 log^1/3 n) by Amit Chakrabarti and Subhash Khot.^[14]

Some recent results give lower bounds which are determined by the critical probability p of the monotone graph property under consideration. The critical probability p is defined as the unique p such that such that a random graph G(n, p) possesses this property with probability equal to 1/2. A random graph G(n, p) is a graph on n vertices where each edge is chosen to be present with probability p independent of all the other edges. In 2002, Ehud Friedgut, Jeff Kahn and Avi Wigderson showed a lower bound of for a monotone graph property with critical probability p.^[15] In 2005, O'Donnell, Saks, Schramm and Servedio showed a lower bound of Ω(n^4/3/p^1/3).^[16]

As in the deterministic case, there are many special properties for which an Ω(n²) lower bound is known. Moreover, better lower bounds are known for several classes of graph properties. For instance, for testing whether the graph has a subgraph isomorphic to any given graph (the so-called subgraph isomorphism problem), the best known lower bound is Ω(n^3/2) due to Gröger.^[17]

[edit] Quantum query complexity

For bounded-error quantum query complexity, the best known lower bound is Ω(n^2/3 log^1/6 n) as observed by Andrew Yao.^[18] It is obtained by combining the randomized lower bound with the quantum adversary method. The best possible lower bound one could hope to achieve is Ω(n), unlike the classical case, due to Grover's algorithm which gives a O(n) query algorithm for testing the monotone property of non-emptiness. Similar to the deterministic and randomized case, there are some properties which are known to have an Ω(n) lower bound, for example non-emptiness (which follows from the optimality of Grover's algorithm) and the property of containing a triangle.^[18] More interestingly, there are some graph properties which are known to have an Ω(n^3/2) lower bound, and even some properties with an Ω(n²) lower bound. For example, the monotone property of nonplanarity has an Ω(n^3/2) lower bound^[19] and the monotone property of containing more than half the possible number of edges (also called the majority function) has an Ω(n²) lower bound.^[20]

[edit] Further reading

• Laszlo Lovasz; Young, Neal E. (2002). "Lecture Notes on Evasiveness of Graph Properties". arΧiv:cs/0205031v1 [cs.CC]. 
• Chronaki, Catherine E (1990). A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.1041. Retrieved 2009-10-10. 
• Michael Saks. "Decision Trees: Problems and Results, Old and New". http://www.math.rutgers.edu/~saks/PUBS/dtsurvey.pdf. 

[edit] References