TY - GEN

T1 - Permutation property testing under different metrics with low query complexity

AU - Fox, Jacob

AU - Wei, Fan

N1 - Publisher Copyright:
Copyright © by SIAM.

PY - 2017

Y1 - 2017

N2 - The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with constant" query complexity, depending only on and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques are often enormous and impractical. It remains a major open problem if better bounds hold. Hoppen, Kohayakawa, Moreira, and Sampaio conjectured and Klimosova and Kral' proved that hereditary permutation properties are strongly testable, i.e., can be tested with respect to Kendall's tau distance. The query complexity bound coming from this proof is huge. Even for testing a single forbidden sub permutation it is of Ackermann-type in 1= We give a new proof which gives a polynomial bound in 1= for testing a single forbidden subpermutation. Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1/ query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden sub permutation for the property. Finally, we show that several different permutation metrics of interest are related to the rectangular distance, yielding similar results for testing with respect to these metrics.

AB - The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with constant" query complexity, depending only on and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques are often enormous and impractical. It remains a major open problem if better bounds hold. Hoppen, Kohayakawa, Moreira, and Sampaio conjectured and Klimosova and Kral' proved that hereditary permutation properties are strongly testable, i.e., can be tested with respect to Kendall's tau distance. The query complexity bound coming from this proof is huge. Even for testing a single forbidden sub permutation it is of Ackermann-type in 1= We give a new proof which gives a polynomial bound in 1= for testing a single forbidden subpermutation. Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1/ query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden sub permutation for the property. Finally, we show that several different permutation metrics of interest are related to the rectangular distance, yielding similar results for testing with respect to these metrics.

UR - http://www.scopus.com/inward/record.url?scp=85016222194&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016222194&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.107

DO - 10.1137/1.9781611974782.107

M3 - Conference contribution

AN - SCOPUS:85016222194

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1618

EP - 1637

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -