Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-642-38233-8_25
Title: | Query complexity of matroids | Authors: | Kulkarni, R. Santha, M. |
Keywords: | (parity, randomized, quantum) decision tree complexity AC0 Fourier spectrum matroids read-once formulae |
Issue Date: | 2013 | Citation: | Kulkarni, R.,Santha, M. (2013). Query complexity of matroids. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7878 LNCS : 300-311. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-38233-8_25 | Abstract: | Let M be a bridgeless matroid on ground set {1,...,n} and fM : {0,1}n → {0,1} be the indicator function of its independent sets. A folklore fact is that fM is evasive, i.e., D(fM) = n where D(fM) denotes the deterministic decision tree complexity of f. Here we prove query complexity lower bounds for fM in three stronger query models: (a) where D⊕(fM) = Ω(n), where D⊕(f) denotes the parity decision tree complexity of f; (b) R(fM) = Ω(n/log n), where R(f) denotes the bounded error randomized decision tree complexity of f; and (c) Q(f M) = Ω(√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. © 2013 Springer-Verlag. | Source Title: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | URI: | http://scholarbank.nus.edu.sg/handle/10635/117268 | ISBN: | 9783642382321 | ISSN: | 03029743 | DOI: | 10.1007/978-3-642-38233-8_25 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.