Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-063 | 17th May 2012 21:37

#### Query complexity of matroids

TR12-063
Authors: Raghav Kulkarni, Miklos Santha
Publication: 17th May 2012 23:01
Keywords:

Abstract:

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove query complexity lower bounds for $f_\mathcal{M}$ in three stronger query models: (a) $D_\oplus(f_\mathcal{M}) = \Omega(n),$ where $D_\oplus(f)$ denotes the parity decision tree complexity of $f;$ (b) $R(f_\mathcal{M}) = \Omega(n / \log n),$ where $R(f)$ denotes the bounded error randomized decision tree complexity of $f;$ and (c) $Q(f_\mathcal{M}) = \Omega(\sqrt 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, O'Donnell, Servedio, Shpilka, and Wimmer 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 (cf. Shi and Zhang) 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.

Keywords: (parity, randomized, quantum) decision tree complexity, matroids, Fourier spectrum, read-once formulae, $AC^0$

ISSN 1433-8092 | Imprint