Let @math be a fixed graph on @math vertices. Let @math iff the input graph @math on @math vertices contains @math as a (not necessarily induced) subgraph. Let @math denote the cardinality of a maximum independent set of @math . In this paper we show: [Q(f_H) = ( n ), ] where @math denotes the quantum query complexity of @math . As a consequence we obtain a lower bounds for @math in terms of several other parameters of @math such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that @math for any @math , improving on the previously best known bound of @math . Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our @math bound for @math matches the square root of the current best known bound for the randomized query complexity of @math , which is @math due to Gr "oger. Interestingly, the randomized bound of @math for @math still remains open. We also study the Subgraph Homomorphism Problem, denoted by @math , and show that @math . Finally we extend our results to the @math -uniform hypergraphs. In particular, we show an @math bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known @math bound. For the Subgraph Homomorphism, we obtain an @math bound for the same.
Understanding the query complexity of monotone graph properties has a long history. In the deterministic setting the Aanderaa-Rosenberg-Karp Conjecture asserts that one must query all the @math edges in the worst-case. The randomized complexity of monotone graph properties is conjectured to be @math . Yao @cite_4 obtained the first super-linear lower bound in the randomized setting using the graph packing arguments. Subsequently his bound was improved by King @cite_6 and later by Hajnal @cite_13 . The current best known bound is @math due to Chakrabarti and Khot @cite_18 . Moreover, O'Donnell, Saks, Schramm, and Servedio @cite_3 also obtained an @math bound via a more generic approach for monotone transitive functions. Friedgut, Kahn, and Wigderson @cite_16 obtain an @math bound where the @math is the critical probability of the property. In the quantum setting, Buhrman, Cleve, de Wolf and Zalka @cite_10 were the first to study quantum complexity of graph properties. Santha and Yao @cite_14 obtain an @math bound for general properties. Their proof follows along the lines of Hajnal's proof.
@cite_18 @cite_14 @cite_4 @cite_10 @cite_3 @cite_6 @cite_16 @cite_13
2041763757 2950902318 1965171998 1582919494 2101724873
For any property P on n-vertex graphs, let C(P) be the minimum number of edges that need to be examined by any decision tree algorithm for determining P. In 1975 Rivest and Vuillemin settled the Aanderra-Rosenberg Conjecture, proving that C(P) = Ω(n2) for every nontrivial monotone graph property P. An intriguing open question is whether the theorem remains true when randomized algorithms are allowed. In this paper we report progress on this problem, showing that Ω(n(log n)1 12) edges must be examined by a randomized algorithm for determining any nontrivial monotone graph property. We prove that for any decision tree calculating a boolean function @math , [ [f] i=1 ^n (f), ] where @math is the probability that the @math th input variable is read and @math is the influence of the @math th variable on @math . The variance, influence and probability are taken with respect to an arbitrary product measure on @math . It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced boolean function with a decision tree of depth @math has a variable with influence at least @math . The only previous nontrivial lower bound known was @math . Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with non-boolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least @math , where @math is the number of vertices and @math is the critical threshold probability. This supersedes the milestone @math bound of Hajnal and is sometimes superior to the best known lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson. In this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes 1, 2, …, n has a given property by asking questions of the form “Is edge in the graph?”. The complexity of a property is the number of questions which must be asked in the worst case. Aanderaa and Rosenberg conjectured that any monotone, nontrivial, (isomorphism-invariant) n-node digraph property has complexity O( n 2 ). This bound was proved by Rivest and Vuillemin and subsequently improved to n 2 4+ o ( n 2 ). In Part I, we give a bound of n 2 2+ o ( n 2 ). Whether these properties are evasive remains open. In Part II, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next edge to be queried. Yao's lower bound on the randomized complexity of any monotone nontrivial graph property is improved from O( n log 1 12 n ) to O( n 5 4 ), and improved bounds for the complexity of monotone, nontrivial bipartite graph properties are shown. We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of A, namely the value of p for which a random graph from G(n,p) has property A with probability 1 2. Then the expected number of queries made by any decision tree for A on such a random graph is at least Ω(n 2 max pn, logn ). We improve King's Ω(n5 4) lower bound on the randomized decision tree complexity of monotone graph properties to Ω(n4 3). The proof follows Yao's approach and improves it in a different direction from King's. At the heart of the proof are a duality argument combined with a new packing lemma for bipartite graphs.