Abstract
Let \(\mathcal{M}\) be a bridgeless matroid on ground set {1,...,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 ⊕ (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 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Barnum, H., Saks, M.E.: A lower bound on the quantum query complexity of read-once functions. J. Comput. Syst. Sci. 69(2), 244–258 (2004)
Beigel, R.: The Polynomial Method in Circuit Complexity. In: Structure in Complexity Theory Conference, pp. 82–95 (1993)
Bernasconi, A., Codenotti, B.: Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem. IEEE Trans. Computers 48(3), 345–351 (1999)
Björner, A.: Matroid Applications (ch. 7.). In: Homology and Shellability of Matroids and Geometric Lattices, pp. 226–283 (1992)
Björner, A., Lovász, L., Yao, A.C.-C.: Linear Decision Trees: Volume Estimates and Topological Bounds. In: STOC 1992, pp. 170–177 (1992)
Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Information. Contemporary Mathematics, vol. 305, pp. 53–74. AMS (2002)
Buhrman, H., de Wolf, R.: Communication Complexity Lower Bounds by Polynomials. In: IEEE Conference on Computational Complexity, pp. 120–130 (2001)
Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. 288(1), 21–43 (2002)
Childs, A.M., Kothari, R.: Quantum query complexity of minor-closed graph properties. In: STACS 2011, pp. 661–672 (2011)
Coullard, C.R., Hellerstein, L.: Independence and Port Oracles for Matroids, with an Application to Computational Learning Theory. Combinatorica 16(2), 189–208 (1996)
Gopalan, P., O’Donnell, R., Servedio, R.A., Shpilka, A., Wimmer, K.: Testing Fourier Dimensionality and Sparsity. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 500–512. Springer, Heidelberg (2009)
Lov, K.,, G.: A Fast Quantum Mechanical Algorithm for Database Search. In: STOC 1996, pp. 212–219 (1996)
Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC0. In: SODA 2012, pp. 961–972 (2012)
Jain, R., Klauck, H.: The Partition Bound for Classical Communication Complexity and Query Complexity. In: IEEE Conference on Computational Complexity, pp. 247–258 (2010)
Kahn, J., Saks, M.E., Sturtevant, D.: A topological approach to evasiveness. Combinatorica 4(4), 297–306 (1984)
Kleinschmidt, P., Onn, S.: Signable Posets and Partitionable Simplicial Complexes. Discrete and Computational Geometry 15(4), 443–466 (1996)
Kook, W.: A new formula for an evaluation of the Tutte polynomial of a matroid. Discrete Mathematics 300(1-3), 235–238 (2005)
Kushilevitz, E., Mansour, Y.: Learning Decision Trees Using the Fourier Spectrum. SIAM J. Comput. 22(6), 1331–1348 (1993)
Leonardos, N., Saks, M.: Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity 19(2), 153–181 (2010)
Montanaro, A., Osborne, T.: On the communication complexity of XOR functions. CoRR abs/0909.3392 (2009)
Nisan, N., Szegedy, M.: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4, 301–313 (1994)
Nisan, N., Wigderson, A.: On Rank vs. Communication Complexity. Combinatorica 15(4), 557–565 (1995)
Rivest, R.L., Vuillemin, J.: On Recognizing Graph Properties from Adjacency Matrices. Theor. Comput. Sci. 3(3), 371–384 (1976)
Shi, Y., Zhang, Z.: Communication Complexities of XOR functions CoRR abs/0808.1762 (2008)
Simon, D.R.: On the Power of Quantum Computation. SIAM J. Comput. 26(5), 1474–1483 (1997)
Szegedy, B., Szegedy, C.: Symplectic Spaces And Ear-Decomposition Of Matroids. Combinatorica 26(3), 353–377 (2006)
Zhang, Z., Shi, Y.: On the parity complexity measures of Boolean functions. Theor. Comput. Sci. 411(26-28), 2612–2618 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kulkarni, R., Santha, M. (2013). Query Complexity of Matroids. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-38233-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38232-1
Online ISBN: 978-3-642-38233-8
eBook Packages: Computer ScienceComputer Science (R0)