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.

SCOPUSTM   
Citations

5
checked on Nov 16, 2018

Page view(s)

58
checked on Nov 16, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.