Query Complexity of Matroids

摘要

Let M be a bridgeless matroid on ground set {1, ..., n} and f_M : {0, 1}~n → {0, 1} be the indicator function of its independent sets. A folklore fact is that f_M is evasive, i.e., D(f_M) = n where D(f) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for f_M in three stronger query models: (a) D_(direct+)(f_M) = Ω(n), where D_(direct+)(f) denotes the parity decision tree complexity of f; (b) R(f_M) = Ω(n/log n), where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) Q(f_M) = Ω({the square root of}n), where Q(f) denotes the bounded error quantum query complexity of f. To prove (a) we propose a method to lower bound the sparsity of a Boolean function by upper bounding its partition size. Our method yields a new application of a somewhat surprising result of Gopalan et al. [11] that connects the sparsity to the granularity of the function. As another application of our method, we confirm the Log-rank Conjecture for XOR functions [27], up to a poly-logarithmic factor, for a fairly large class of AC~0- XOR functions. To prove (b) and (c) we relate the ear decomposition of matroids to the critical inputs of appropriate tribe functions and then use the existing randomized and quantum lower bounds for these functions.