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$