ECCC-Report TR10-136https://eccc.weizmann.ac.il/report/2010/136Comments and Revisions published for TR10-136en-usFri, 27 Aug 2010 19:39:13 +0300
Revision 1
| Separations of Matroid Freeness Properties |
Jakob NordstrÃ¶m,
Arnab Bhattacharyya,
Ning Xie,
Elena Grigorescu
https://eccc.weizmann.ac.il/report/2010/136#revision1Properties of Boolean functions on the hypercube that are invariant with respect to linear transformations of the domain are among some of 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 of matroid freeness properties. One question that has been left open, however, is whether the infinitely many syntactically different matroid freeness properties recently shown to be testable in fact correspond to new, semantically distinct properties. This is a crucial issue since it has also been shown previously that there exist subclasses of matroid freeness 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" from one another. 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 explicit functions that are far in Hamming distance from all functions lying in the lower levels of the hierarchy. Our key technical tool is an apparently new notion of maps between linear matroids, which we call labeled matroid homomorphisms, that might be of independent interest.
Fri, 27 Aug 2010 19:39:13 +0300https://eccc.weizmann.ac.il/report/2010/136#revision1
Paper TR10-136
| Separations of Matroid Freeness Properties |
Jakob NordstrÃ¶m,
Arnab Bhattacharyya,
Ning Xie,
Elena Grigorescu
https://eccc.weizmann.ac.il/report/2010/136Properties of Boolean functions on the hypercube that are invariant
with respect to linear transformations of the domain are among some of
the most well-studied properties in the context of property testing.
In this paper, we study a particular natural class of linear-invariant
properties, called matroid freeness properties. These properties have
all been conjectured to be testable, and a recent sequence of works
have established testability for increasingly larger subclasses of
matroid freeness properties. One question that has been left open,
however, is whether the infinitely many syntactically different
matroid freeness properties recently shown to be testable in fact
correspond to new, semantically distinct properties. This is a crucial
issue since it has also been shown previously that there exist
subclasses of matroid freeness 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" from one another. 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
explicit functions that are far in Hamming distance from all functions
lying in the lower levels of the hierarchy. Our key technical tool is
an apparently new notion of maps between linear matroids, which we
call labeled matroid homomorphisms, that might be of independent
interest.
Thu, 26 Aug 2010 13:07:22 +0300https://eccc.weizmann.ac.il/report/2010/136