Block Sensitivity of Minterm-Transitive Functions Andrew Drucker MIT 0 January 13, 2010 1 0 2 n Abstract a J Boolean functions with symmetry properties are interesting from a complexity the- 3 ory perspective; extensive research has shown that these functions, if nonconstant, 1 must have high ‘complexity’ according to various measures. ] Inrecentworkofthis type,Sungave boundsontheblocksensitivity ofnonconstant C Boolean functions invariant under a transitive permutation group. Sun showed that C all such functions satisfy bs(f) = Ω(N1/3), and that there exists such a function for . s whichbs(f)= O(N3/7lnN). His examplefunctionbelongs toasubclassoftransitively c [ invariant functions called the minterm-transitive functions (defined in earlier work by Chakraborty). 1 v We extend these results in two ways. First, we show that nonconstant minterm- 2 transitive functions satisfy bs(f) = Ω(N3/7). Thus Sun’s example function has nearly 5 minimal block sensitivity for this subclass. Second, we give an improved example: a 0 2 minterm-transitive function for which bs(f)= O(N3/7ln1/7N). . 1 0 0 1 Introduction 1 : v Boolean functions, like other objects in mathematics, can be classified according to the sym- i X metries they possess. A natural notion of symmetry arises when we consider permutations r of the input variables. Given a function f : 0,1 N 0,1 and a permutation σ on a { } → { } 1,...,N , we say that f is invariant under σ if permuting the input variables according { } to σ never affects the value of f. For every function f it is easily seen that the set of permutations under which f is invariant forms a group, the invariance group of f. One class of ‘high-symmetry’ functions are those whose invariance group is transitive: a permutation group Γ is transitive if for each i,j [N] there is a π Γ such that π(i) = j. ∈ ∈ Transitively invariant Boolean functions (also called ‘weakly symmetric functions’) are a natural, important class which includes graph properties and symmetric functions. They are of particular interest in computational complexity: several decades of research have shown that certain classes of (nonconstant) transitively invariant Boolean functions have high ‘complexity’ in several senses. For example, symmetric functions on N inputs have randomized query complexity Ω(N), quantum query complexity Ω(√N) [2], and sensitivity 1 Ω(N), while graph properties on n-vertex graphs have deterministic query complexity Ω(n), quantum query complexity Ω(n1/2) [11], and sensitivity Ω(n) [12]. In each case the lower bound obtained is tight (except for a log-factor uncertainty in the case of [11]). For general transitively invariant functions, the deterministic and quantum query com- plexities have also been pinpointed fairly precisely [11]; however, the sensitivity and block sensitivity of these functions are less well understood. In particular, it is open whether such functions have sensitivity s(f) = NΩ(1). A version of this question was first asked by Turan in 1984 [12], who gave an affirmative answer for the case of graph properties. Partial progress on Turan’s question was made by Chakraborty, who in [4] defined a special class of transitively invariant functions called minterm-transitive functions (see Sec- tion 2.2 for the definition). These functions are of interest because although they are of restricted form, they place no restriction on the type of transitive invariance group associ- ated with the Boolean function (in contrast to graph properties and symmetric functions). Chakraborty showed that for such functions s(f) = Ω(N1/3), and he also constructed an ex- ample for which this bound is tight. This is the lowest sensitivity known for any transitively invariant function. In subsequent work, Sun [10] showed that for general transitively invariant functions, the block sensitivity bs(f) satisfies bs(f) = Ω(N1/3). Sun also gave an example of a transitively invariant (in fact minterm-transitive) function for which bs(f) = O(N3/7lnN). In this paper, we extend Sun’s results in two directions. First, we show that for minterm- transitive functions, bs(f) = Ω(N3/7). While this does not close the gapin our knowledge for general transitively invariant functions, it in a sense explains why Sun’s upper bound took the form it did. To prove this result (in Section 3), we build on Sun’s approach (which is also related to ideas in [4], [8]) of selecting random permutations from the invariance group for f to find disjoint sensitive blocks. In a novel step, we use the ‘deletion method’ of probabilistic combinatorics [1] to create a large collection of sensitive blocks with ‘low overlap’; we then apply a simple method for passing from an input with many, low-overlap sensitive blocks to an input with many disjoint sensitive blocks. Next, we improve Sun’s upper-bound example, by giving (in Section 4) a family of minterm-transitive functions for which bs(f) = O(N3/7ln1/7N). Our basic approach is the same as Sun’s [10], but we improve part of the construction, using a powerful inequality from probability theory due to Janson and Suen [6]. We introduce this inequality in Section 2.3. 2 Preliminaries For convenience, in this paper we will always regard an N-bit string as having coordinates indexed by Z = 0,1,...,N 1 . N { − } 2.1 Sensitivity and block sensitivity Given a string x 0,1 N and a set B Z (also referred to as a ‘block’), define xB as the N ∈ { } ⊆ string whose ith bit is x if i B, and x otherwise. In particular, let xi denote the string x i i ∈ 2 with its ith bit flipped. For any Boolean function f : 0,1 N 0,1 and x 0,1 N, say that B Z is a N { } → { } ∈ { } ⊆ sensitive block for x if f(xB) = f(x). Define bs(f;x) as the largest d for which there exists 6 d disjoint sensitive blocks B ,...,B Z for x. 1 d N ⊆ For b 0,1 , define the b-block sensitivity of f, or bsb(f), as maxx∈f−1(b)bs(f;x). Define ∈ { } the block sensitivity bs(f) = max(bs (f),bs (f)). Block sensitivity was first defined by Nisan 0 1 in [7]. The sensitivity of f, denoted s(f), is defined identically to bs(f), but with the further restriction that all sensitive blocks considered must be of size 1 (thus s(f) bs(f)). Sen- ≤ sitivity, a concept which predates block sensitivity, was defined in [5] (and originally called ‘critical complexity’). 2.2 Patterns, permutations, and invariance Define a pattern as a string p 0,1, N (note, this definition includes the ordinary strings ∈ { ∗} x 0,1 N), and define the domain of p, denoted dom(p), as dom(p) = i : p 0,1 . i ∈ { } { ∈ { }} We say that p is defined on i if i dom(p). Say that two patterns p,p′ agree if for all i Z , N ∈ ∈ p 0,1 p′ p , . Note that this condition is symmetric in p,p′. i ∈ { } ⇒ i ∈ { i ∗} For a pattern p and a permutation σ from the symmetric group S (considered as the N group of permutations on Z ), define the σ-shift of p, denoted σ(p), by the rule σ(p) = N i pσ−1(i). Similarly, for subsets B ZN, define the σ-shifted set σ(B) = σ(b) : b B . ⊆ { ∈ } Given a permutation group Γ S , we say a Boolean function f is invariant under Γ if N ≤ for all x 0,1 N and σ Γ,f(x) = f(σ(x)). A per∈m{utati}on group Γ∈is called transitive if for all i,j Z there exists σ Γ such that N ∈ ∈ σ(i) = j. An important example of a transitive permutation group is the family of cyclic shifts of the coordinates, which we’ll denote by T = {tj: tj(i) = i+jmodN}j∈ZN. We say a Boolean function f is transitively invariant (or weakly symmetric, in [10]) if it is invariant under some transitive group Γ. We say f is cyclically invariant if it is invariant under . T Given a pattern p and a permutation group Γ S , define the (Γ,p)-pattern matching N ≤ problem fΓ,p : 0,1 n 0,1 by { } → { } fΓ,p(x) = 1 σ Γ : x agrees with σ(p). ⇔ ∃ ∈ Equivalently, fΓ,p(x) = 1 σ Γ such that σ(x) agrees with p. A function f : 0,1 n ⇔ ∃ ∈ { } → 0,1 is called minterm-transitive if there exists a transitive group Γ and pattern p such { } that f = fΓ,p. f is called minterm-cyclic if in addition we may take Γ = . Note that T transitivepattern-matchingfunctionsaretransitivelyinvariant, andminterm-cyclicfunctions are cyclically invariant. (Both of these subclasses were defined in [4], where the terminology is explained.) 3 2.3 A probabilistic inequality The key toolin ourconstruction of aminterm-transitive functionwithlow block sensitivity is a probabilistic inequality from a paper of Janson [6]. This inequality reformulates an earlier result of Suen [9], which in turn generalizes another, earlier result of Janson (see [6] and Alon and Spencer’s book [1, Sec. 8.7] for more details). Roughly speaking, the inequality upper- bounds the probability that a family of indicator random variables sums to zero, provided the expected value of their sum is large enough and they are ‘mostly independent’. We set up and state this inequality (which will be used only in Section 4) next. Let I be a finite family of indicator (i.e., 0/1-valued) random variables on some i i∈I { } probability space Ω. Let G be an (undirected) dependency graph with vertex set (and I edges indicated by , and with i ≁ i for all i). This means that, if A,B are disjoint sets in and i ≁ j for each∼pair (i,j) A B, then the family I must be independent of the i i∈A I ∈ × { } family I . j j∈B For{i } , let q := E[I ], and let µ := E[ I ] = q . Let δ := q . Let δ := max∈δI. and ∆i := i E[I I ], whereit∈hIe isum isio∈vIeri unordeired pairjs:i.∼jOjbserve i i {i,j}:i∼j i j P P P that δ and ∆ measure in a sense the ‘level of dependence’ among the family. Then the P promised inequality is as follows: Theorem 1. [6] Pr[ I = 0] e−µ+∆e2δ. i∈I i ≤ P 3 Lower Bounds on bs(f) for Minterm-Transitive Func- tions In this section we prove: Theorem 2. If f : 0,1 N 0,1 is a nonconstant minterm-transitive function, then { } → { } bs(f) = Ω(N3/7). We will need the following easy observation, essentially due to [8]: Lemma 3. [8] If Γ S is a transitive group of permutations, i Z is any index, and σ N N is a uniformly chose⊆n element of Γ, then σ(i) is uniformly distribu∈ted over Z . N Our main new tool is the following combinatorial lemma. Lemma 4. Let B Z be of size at most N3/7, and let Γ S be a transitive per- N N ⊆ ≤ mutation group. If N is sufficiently large, there exists a T 1N3/7 and group elements Σ = σ ,...,σ Γ such that for each i Z , there are at m≥ost23 indices j T for which 1 T N { } ⊆ ∈ ≤ i σ (B). j ∈ (Note that there is no requirement that the σ all be distinct.) j 4 Proof of Lemma 4. Our strategy is as follows: first we select T permutations σ indepen- 0 j dently at random from Γ, where T := N3/7 . Some indices i will be contained in 4 or more 0 ⌈ ⌉ of the shifted sets σ (B), but we argue that with nonzero probability, we can discard at most j 1N3/7 of the permutations in our collection to ‘fix’ every such index i. 2 So let σ ,...,σ be independent and uniform from Γ. For each i Z , say i is ‘bad’ if 1 T0 ∈ N i σ (B) for at least 4 trials j T . We upper-bound the probability that i is bad. First, j 0 ∈ ≤ for any fixed trial, Lemma 3 tells us that Pr[i σ (B)] = B /N. Independence of the trials j ∈ | | implies that for any fixed 4-tuple of distinct trials (j ,j ,j ,j ) [T ], the probability that 1 2 3 4 0 ∈ i is in the shifted set on each trial is ( B /N)4. Then by a union bound, | | T B 4 (T B )4 ((N3/7 +1)N3/7)4 N−4/7 0 0 Pr[i is bad] | | < | | < , ≤ 4 N4 24N4 ≤ 24N4 23 (cid:18) (cid:19) the last step holding if N is sufficiently large. Summing over all i Z , the expected number N ∈ of bad i’s is less than N3/7/23. By Markov’s bound, the probability that there are N3/7/12 bad indices is less than 1/2. Now say that i Z is ‘terrible’ if i σ (B) for at least 7 indices j T . By reasoning N j 0 ∈ ∈ ≤ similar to the above, the expected number of terrible indices is at most T B 7 (N−1/7)7 0 N | | < N < 1/2 7 N · 7! 1 (cid:18) (cid:19)(cid:18) (cid:19) − for sufficiently large N. So the probability that any terrible index appears is less than 1/2, and we find that with positive probability there are no terrible indices and fewer than N3/7/12 bad indices. We take any such outcome (specified by a sequence σ ,...,σ ) and for each bad index 1 T0 i, delete from the collection all permutations σ such that i σ (B). Since there are no j j ∈ terrible indices, each such deletion removes at most 6 permutations, so the total number of permutations deleted is less than 6 N3/7 12) = N3/7/2. The remaining collection has size · greater than N3/7/2 and satisfies the Lemma’s conclusion. (cid:0) (cid:14) Proof of Theorem 2. Takeanynonconstantminterm-transitivefunctionf = fΓ,p : 0,1 N { } → 0,1 , where Γ is a transitive group and p a pattern. Let B = i : p 0,1 . Without loss i { } { ∈ { }} of generality we may assume that p contains at least B /2 1’s. Then if we let x 0,1 N | | ∈ { } agree with p and equal 0 where p is undefined, we see that f(x) = 1, while f(xi) = 0 for any i such that p = 1. i Thus bs(f) bs(f;x) B /2. If B > N3/7, then bs(f) > N3/7/2. Let us assume ≥ ≥ | | | | now that B N3/7. In this case, Lemma 4 applies to B: there exist group elements | | ≤ Σ = σ ,...,σ Γ (with T 1N3/7) satisfying the Lemma’s conclusions. Let Σ(p) = { 1 T} ⊆ ≥ 2 σ (p) : σ Σ denote our distinguished set of shifted patterns, and let = B = σ (B) j j Σ j j { ∈ } B { } denote the corresponding collection of domains. Consider the set U Z of indices i appearing in at least two sets B . At most N j Σ ⊆ ∈ B three patterns σ (p) Σ(p) from our collection are defined on any given index, so for each j ∈ i U we can select a value v 0,1 such that at most one σ (p) that is defined on i i j ∈ ∈ { } disagrees with the setting v there. i 5 Let us do the following: Initialize x 0,1 N to any value such that f(x) = 0. • ∈ { } If there exists some i U such that x = v , and such that f(xi) = 0, pick such an i i i • ∈ 6 arbitrarily and set x xi; otherwise halt. ← Repeat the previous step until we halt. • Note that f(x) = 0 for every value of x during the algorithm’s run. Note also that the algorithm must halt, since each step reduces the number of disagreements between x and thev ’s. Nowweaskthefollowingquestion: lookingatthefinalvalueofxwhenthealgorithm i halts, how many i U are such that x still disagrees with v ? Call these indices ‘stubborn’. i i ∈ First, suppose there are at least N3/7/12 stubborn indices. Since we halted, it must be the case that f(xi) = 1 = f(x) for each such stubborn index i, and thus bs(f) bs(f;x) 6 ≥ ≥ N3/7/12. On the other hand, suppose there are fewer than N3/7/12 stubborn indices. As each index i Z appears in at most 3 sets from , fewer than N3/7/4 patterns from Σ(p) N Σ ∈ B contain any stubborn index. If B contains no stubborn indices, call it ‘stubborn-free’; j Σ ∈ B so, there are more than T N3/7/4 N3/7/4 stubborn-free sets B . j − ≥ For each B define the ‘disagreement set’ D = i : σ (p) 0,1 x = σ (p) j Σ j j i i j i ∈ B { ∈ { }∧ 6 } ⊆ B . Each D is nonempty, since f(x) = 0 and f = fΓ,p. Also, f(xDj) = 1 = f(x). j j 6 Observe that if B is stubborn-free, and i D , then σ (p) is the only pattern in Σ(p) j j j ∈ that disagrees with x at i. Thus if Bj,Bj′ are stubborn-free, Dj Dj′ = , so bs(f;x) is at ∩ ∅ least the number of stubborn-free sets B , which we’ve seen is at least N3/7/4. j Σ ∈ B Combining all of our cases, we find that bs(f) = Ω(N3/7). 4 Improved Upper-Bound Example for bs(f) Sun [10] gave an example of a minterm-cyclic function with block sensitivity O(N3/7lnN). This was the lowest block sensitivity known for any non-constant transitively invariant func- tion. In this section we prove the following result, improving on Sun’s example: Theorem 5. There exist a family of nonconstant, minterm-transitive (in fact minterm- cyclic) functions f : 0,1 N 0,1 , such that bs(f ) = O(N3/7ln1/7N). N N { } → { } Most steps of our proof follow the outline of Sun’s, but for completeness we give a self- contained proof. Before defining the p we will use to define f = fT,p, we give two lemmas N (both from [10]) for upper-bounding the block sensitivity of such functions. Lemma 6. [10] For any f = fT,p,bs (f) dom(p) . 1 ≤ | | Proof. Note if f(x) = 1 then some shift t (p) of p agrees with x. So any collection of disjoint j0 blocks B for which f(xBj) = 0 must assign a distinct coordinate from dom(t (p)) to each { j} j0 B , and dom(t (p)) = dom(p) . This proves the Lemma. j | j0 | | | 6 Obtaining an upper bound on bs (f) takes a bit more work. We give some preparatory 0 definitions. By a 4-set in Z we mean a subset of Z of size 4. If A = a ,...,a is a N N 1 4 { } 4-set, say that pattern p contains a balanced shifted copy of A if there exists a cyclic shift t j such that the shifted pattern t (p) satisfies dom(t (p)) A, and t (p) equals 0 on some two j j j ⊇ of the coordinates in A and equals 1 on the other two. Lemma 7. [10] For any f = fT,p, if bs (f) d then there exists a set S Z of size d, 0 N ≥ ⊆ such that there is no 4-set A S for which p contains a balanced shifted copy of A. ⊆ Proof. Say bs (f) d; then there exists an x and d disjoint subsets B ,...,B Z such 0 1 d N that f(xBk) = 1 =≥f(x), for 1 k d. Thus for each k there exists j(k) Z suc⊆h that xBk N 6 ≤ ≤ ∈ agrees with tj(k)(p). If k = k′ yet j(k) = j(k′), then both of Bk,Bk′ would contain each of the 6 (nonempty set of) coordinates on which t (p) disagrees with x, contradicting disjointness; j(k) so the indices j(1),...,j(d) are all distinct. Let J = j(k) denote this index-set ( J = d). { } | | Let S := J = j : j J (all arithmetic in this section is mod N). We claim − {− ∈ } that if A is any 4-set contained in S, then p contains no balanced shifted copy of A. For suppose it did; that is, suppose there exists some j∗ Z such that distinct indices N ∈ j(k1), j(k2), j(k3), j(k4) are in the domain of tj∗(p), and that (renaming the ki’s if − − − − necessary) tj∗(p)−j(k1) = tj∗(p)−j(k2) = 0 while tj∗(p)−j(k3) = tj∗(p)−j(k4) = 1. Equivalently, p−j(k1)−j∗ = p−j(k2)−j∗ = 0 and p−j(k3)−j∗ = p−j(k4)−j∗ = 1. Now for i ∈ [4], recall that xBki agrees with tj(ki)(p). In particular, xB−kji∗ = tj(ki)(p)−j∗, i.e., xB−kji∗ = p−j(ki)−j∗. We have seen that for i = 1,2 the right-hand side equals 0, and for i = 3,4 the right-hand side equals 1. Thus the index j∗ must be contained in exactly two of the sets B ,...,B , − k1 k4 contradicting the fact that they are disjoint. Thus p contains no balanced shifted copy of any 4-set A S. ⊆ We can now explain our strategy (following [10]) to prove Theorem 5: we build a pattern p 0,1, N with ‘small’ domain, so that bs (fT,p) is small by Lemma 6. We choose p such 1 ∈ { ∗} that for any ‘sufficiently large’ S Z , p contains a balanced shifted copy of some 4-set N ⊆ A S; this will bound bs (fT,p) by Lemma 7. 0 ⊆ Our pattern p will have all of its 0/1 entries on 0,1,...,2K 2 , where K = K < N/2 N { − } is a parameter. In this we are following [10], but with some further optimization in our setting of K. The key properties we need in p are provided by the following Lemma: Lemma 8. For sufficiently large K, there is a pattern p with dom(p) 0,1,...,2K 2 ⊆ { − } which contains a shifted balanced copy of every 4-set A 0,1,...,K 1 , and such that ⊆ { − } dom(p) 3K3/4ln1/4K. | | ≤ Note that the ‘sufficiently large’ requirement in Lemma 8 is independent of N. This Lemma resembles [10, Lemma 2], but uses a different construction and improves its param- eters. Sun defined a pattern p by randomly assigning 0/1 values to a collection of translates of an explicit set; by contrast, we use a fully probabilistic construction. We defer the proof of Lemma 8. 7 Proof of Theorem 5. Set K := N4/7 . Fix a p as guaranteed by Lemma 8 (for each suffi- ⌈ln1/7N⌉ ciently large N). Let fT,p be the corresponding minterm-cyclic pattern-matching problem. First, by Lemma 6, bs (fT,p) 3K3/4(lnK)1/4 1 ≤ 4 3 N7·4 = O (lnN)1/4 = O N3/7ln1/7N , (lnN)17·34 · ! (cid:16) (cid:17) since 1 3 = 1. 4 − 28 7 To upper-bound bs (fT,p), let S Z be any set of size at least 4N3/7ln1/7N 4N. 0 ⊆ N ≥ K Following [10], if we pick an interval [a,a+K 1] (mod N) by choosing a Z uniformly, N − ∈ the expected number of elements of S in the interval is at least K 4N/K = 4; therefore there · N exists some such interval which contains at least 4 elements of S. Let A S be these 4 ⊆ elements; since A lie in an interval of length K, Lemma 8 tells us that p contains a balanced shifted copy of A. AsS wasanarbitrarysetofsize 4N3/7ln1/7N,itfollowsfromLemma7thatbs (fT,p) < 0 ≥ 4N3/7ln1/7N, and hence that bs(fT,p) = O(N3/7ln1/7N). This proves Theorem 5. Proof of Lemma 8. We construct p as follows: for each 0 i 2K 2, we independently ≤ ≤ − set p , where for b 0,1 we have Pr[p = b] = (lnK)1/4; with the remaining probability we i ∈ { } i K set p = . i ∗ NowwepreparetoapplyTheorem1fromSection2.3. Fixany4-setA 0,1,...,K 1 . ⊆ { − } For 0 i K 1, let I be the event that A+i is contained in the domain of p and receives i ≤ ≤ − a balanced coloring by p (note that A+i 0,1,...2K 2 ). We will use Theorem 1 to ⊆ { − } upper-bound the probability that I = 0; then we will simply take a union bound over i∈I i all possible choices of A. We define I I to hold iff i = j and (A+i) (A+j) = . Note i j P ∼ 6 ∩ 6 ∅ that this defines a valid dependency graph since p is chosen according to a product measure. Let us compute µ for our family of random variables. Note that each translate A + i can be given a balanced coloring by p in 4 = 6 ways, and that each such coloring has 2 probability ((lnK)1/4)4 = lnK. Thus q = 6lnK and µ = 6lnK. K K i K(cid:0) (cid:1) Now we bound δ and ∆. Note that each translate A+i overlaps with at most 3 others, so that we clearly have δ = o(1). Also, for each pair A+i,A+j of overlapping translates, there are certainly no more than 4 2/2 = 18 colorings of (A+i) (A+j) that make both 2 ∪ translates balanced, and the probability of each one occurring is at most ((lnK)1/4)5 (since (cid:0) (cid:1) K (A+i) (A+j) 5). There are at O(K) such pairs; thus, | ∪ | ≥ ln5/4K ∆ = E[I I ] O K = o(1). i j ≤ · K5/4 ! {i,j}:i∼j X Theorem 1 then tells us that Pr[ I = 0] e−6lnK+o(1) = (1+o(1))K−6. This is less than i i ≤ K−4 for large enough K. P There are K < K4/24 4-sets A 0,1,...,K 1 , so for large enough K, the prob- 4 ⊆ { − } ability that p fails to contain a balanced shifted copy of any such A is, by a union bound, (cid:0) (cid:1) 8 at most 1/24. Also, the expected domain size of p is 2K (lnK)1/4 = 2K3/4ln1/4K. Using · K Markov’s inequality, the probability that dom(p) > 3K3/4ln1/4K is less than 2/3. By a | | union bound we find that with nonzero probability, p contains a balanced shifted copy of each 4-set A 0,1,...,K 1 , and simultaneously dom(p) 3K3/4ln1/4K. This proves ⊆ { − } | | ≤ Lemma 8 (and completes the proof of Theorem 5). 5 Open Problems It seems natural to wonder if the parameters in Lemma 8 can be improved further to remove the log factor entirely. (If so, we suspect a non-probabilistic approach is needed.) This would yield a tight bound of Θ(N3/7) for the minimum achievable block sensitivity for nonconstant minterm-transitive functions. More broadly, we still hope for a better understanding of the sensitivity and block sen- sitivity of general transitively invariant functions. The premier open problem in this area is whether for such functions s(f) = NΩ(1); it is unsolved even for the special case of cyclically invariant functions. References [1] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008. [2] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. In FOCS, pages 352–361, 1998. [3] HarryBuhrmanandRonalddeWolf. Complexitymeasuresanddecisiontreecomplexity: a survey. Theor. Comput. Sci., 288(1):21–43, 2002. [4] Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. In IEEE Conference on Computational Complexity, pages 163–167, 2005. [5] Stephen Cook, Cynthia Dwork, and Ru¨diger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput., 15(1):87–97, 1986. [6] Svante Janson. New versions of suen’s correlation inequality. Random Struct. Algo- rithms, 13(3-4):467–483, 1998. [7] Noam Nisan. Crew prams and decision trees. SIAM J. Comput., 20(6):999–1007, 1991. [8] Ronald L. Rivest and Jean Vuillemin. On recognizing graph properties from adjacency matrices. Theor. Comput. Sci., 3(3):371–384, 1976. 9 [9] Stephen Suen. A correlation inequality and a poisson limit theorem for nonoverlapping balancedsubgraphs ofarandomgraph. Random Struct. Algorithms, 1(2):231–242,1990. [10] Xiaoming Sun. Block sensitivity of weakly symmetric functions. Theor. Comput. Sci., 384(1):87–91, 2007. [11] Xiaoming Sun, Andrew Chi-Chih Yao, and Shengyu Zhang. Graph properties and circular functions: How low can quantum query complexity go? In IEEE Conference on Computational Complexity, pages 286–293, 2004. [12] Gy¨orgy Tura´n. The critical complexity of graph properties. Inf. Process. Lett., 18(3):151–153, 1984. 10