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