Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T14:05:29.625Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast Property Testing and Metrics for Permutations

Part of: Extremal combinatorics Combinatorics Discrete mathematics in relation to computer science Algorithms - Computer Science

Published online by Cambridge University Press:  24 May 2018

JACOB FOX  and
FAN WEI
JACOB FOX
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: [email protected], [email protected])
FAN WEI
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 is often enormous and impractical. It remains a major open problem if better bounds hold.

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 subpermutation 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.

MSC classification

Primary: 68W20: Randomized algorithms
Secondary: 68R05: Combinatorics 05D40: Probabilistic methods 05A05: Permutations, words, matrices 68R15: Combinatorics on words
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 539 - 579
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N. (2002) Testing subgraphs in large graphs. Random Struct. Alg. 21 359–370.CrossRefGoogle Scholar
[2] Alon, N. and Fox, J. (2015) Easily testable graph properties. Combin. Probab. Comput. 24 646–657.Google Scholar
[3] Alon, N. and Shapira, A. (2006) A characterization of easily testable induced subgraphs. Combin. Probab. Comput. 15 791–805.CrossRefGoogle Scholar
[4] Alon, N. and Shapira, A. (2008) A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 1703–1727.CrossRefGoogle Scholar
[5] Conlon, D. and Fox, J. (2012) Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22 1191–1256.Google Scholar
[6] Conlon, D. and Fox, J. (2013) Graph removal lemmas. In Surveys in Combinatorics 2013, Vol. 409 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 1–49.Google Scholar
[7] Cooper, J. N. (2006) A permutation regularity lemma. Electron. J. Combin. 13 R22.Google Scholar
[8] Diaconis, P. personal communication.Google Scholar
[9] Diaconis, P. (1988) Group Representations in Probability and Statistics, Vol. 11 of Lecture Notes Monograph Series, Institute of Mathematical Statistics.Google Scholar
[10] Diaconis, P. and Graham, R. L. (1977) Spearman's footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B 39 262–268.Google Scholar
[11] Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463–470.Google Scholar
[12] Fox, J. Stanley–Wilf limits are typically exponential. Adv. Math., to appear.Google Scholar
[13] Fox, J. and Lovász, L. M. (2016) A tight bound for Green's arithmetic triangle removal lemma in vector spaces. Adv. Math. 321 287–297.Google Scholar
[14] Fox, J., Lovász, L. M. and Zhao, Y. (2016) On regularity lemmas and their algorithmic applications. Combin. Probab. Comput. 26 481–505.Google Scholar
[15] Fox, J. and Wei, F. Strongly testing hereditary permutation properties with polynomial query complexity. In preparation.Google Scholar
[16] Füredi, Z. and Hajnal, P. (1992) Davenport–Schinzel theory of matrices. Discrete Math. 103 233–251.Google Scholar
[17] Goldreich, O., Goldwasser, S. and Ron, D. (1998) Property testing and its applications to learning and approximation. J. Assoc. Comput. Mach. 45 653–750.CrossRefGoogle Scholar
[18] Goldreich, O. and Trevisan, L. (2003) Three theorems regarding testing graph properties. Random Struct. Alg. 23 23–57.CrossRefGoogle Scholar
[19] Hoppen, C., Kohayakawa, Y. and Sampaio, R. M. (2012) A note on permutation regularity. Discrete Appl. Math. 160 2716–2727.Google Scholar
[20] Hoppen, C., Kohayakawa, Y., Moreira, C. G., Ráth, B. and Sampaio, R. M. (2013) Limits of permutation sequences. J. Combin. Theory Ser. B 103 93–113.Google Scholar
[21] Hoppen, C., Kohayakawa, Y., Moreira, C. G. and Sampaio, R. M. (2011) Testing permutation properties through subpermutations. Theoret. Comput. Sci. 412 3555–3567.CrossRefGoogle Scholar
[22] Klazar, M. (2000) The Füredi–Hajnal conjecture implies the Stanley–Wilf conjecture. In Formal Power Series and Algebraic Combinatorics (Krob, D., Mikhalev, A. A. and Mikhalev, A. V., eds), Springer, pp. 250–255.CrossRefGoogle Scholar
[23] Klimošová, T. and Král', D. (2012) Hereditary properties of permutations are strongly testable. arXiv:1208.2624 An early version appeared in SODA '14: 25th Annual ACM–SIAM Symposium on Discrete Algorithms, ACM (2014), pp. 1164–1173.Google Scholar
[24] Kruskal, J. B. Jr (1953) Monotonic subsequences. Proc. Amer. Math. Soc. 4 264–273.CrossRefGoogle Scholar
[25] Lovász, L. (2012) Large Networks and Graph Limits, Vol. 60 of American Mathematical Society Colloquium Publications, AMS.Google Scholar
[26] Marcus, A. and Tardos, G. (2004) Excluded permutation matrices and the Stanley–Wilf conjecture. J. Combin. Theory Ser. A 107 153–160.Google Scholar
[27] Monge, G. (1781), Mémoire sur la théorie des déblais et des remblais. Histoire de l'Académie Royale des Sciences de Paris, pp. 666–704.Google Scholar
[28] Rubinfield, R. and Sudan, M. (1996) Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25 252–271.CrossRefGoogle Scholar
[29] Rubner, Y., Tomasi, C. and Guibas, L. J. (2000) The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vision. 40 99–121.Google Scholar
[30] Vaidya, P. (1989) Geometry helps in matching. SIAM J. Comput. 18 1201–1225.Google Scholar