Name
Abstract | ||
|---|---|---|
Properties of Boolean functions on the hypercube invariant with respect to linear transformations of the domain are among the most well-studied properties in the context of property testing. In this paper, we study the fundamental class of linear-invariant properties called matroid freeness properties. These properties have been conjectured to essentially coincide with all testable linear-invariant properties, and a recent sequence of works has established testability for increasingly larger subclasses. One question left open, however, is whether the infinitely many syntactically different properties recently shown testable in fact correspond to new, semantically distinct ones. This is a crucial issue since it has also been shown that there exist subclasses of these properties for which an infinite set of syntactically different representations collapse into one of a small, finite set of properties, all previously known to be testable. An important question is therefore to understand the semantics of matroid freeness properties, and in particular when two syntactically different properties are truly distinct. We shed light on this problem by developing a method for determining the relation between two matroid freeness properties P and Q. Furthermore, we show that there is a natural subclass of matroid freeness properties such that for any two properties P and Q from this subclass, a strong dichotomy must hold: either P is contained in Q or the two properties are "well separated." As an application of this method, we exhibit new, infinite hierarchies of testable matroid freeness properties such that at each level of the hierarchy, there are functions that are far from all functions lying in lower levels of the hierarchy. Our key technical tool is an apparently new notion of maps between linear matroids, called matroid homomorphisms, that might be of independent interest. |
Year | Venue | Keywords |
|---|---|---|
2010 | Electronic Colloquium on Computational Complexity | boolean function,computational complexity,property testing,linear transformation |
DocType | Volume | Citations |
Journal | abs/1008.4401 | 1 |
PageRank | References | Authors |
0.36 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arnab Bhattacharyya | 1 | 214 | 27.99 |
| Elena Grigorescu | 2 | 192 | 24.75 |
| Jakob Nordström | 3 | 177 | 21.76 |
| Ning Xie | 4 | 64 | 16.62 |