Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-10-30T06:06:26.817Z Has data issue: false hasContentIssue false

Fast Property Testing and Metrics for Permutations

Published online by Cambridge University Press:  24 May 2018

JACOB FOX
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: jacobfox@stanford.edu, fanwei@stanford.edu)
FAN WEI
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: jacobfox@stanford.edu, fanwei@stanford.edu)

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.

Type
Paper
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 359370.CrossRefGoogle Scholar
[2] Alon, N. and Fox, J. (2015) Easily testable graph properties. Combin. Probab. Comput. 24 646657.Google Scholar
[3] Alon, N. and Shapira, A. (2006) A characterization of easily testable induced subgraphs. Combin. Probab. Comput. 15 791805.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 17031727.CrossRefGoogle Scholar
[5] Conlon, D. and Fox, J. (2012) Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22 11911256.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. 149.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 262268.Google Scholar
[11] Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463470.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 287297.Google Scholar
[14] Fox, J., Lovász, L. M. and Zhao, Y. (2016) On regularity lemmas and their algorithmic applications. Combin. Probab. Comput. 26 481505.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 233251.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 653750.CrossRefGoogle Scholar
[18] Goldreich, O. and Trevisan, L. (2003) Three theorems regarding testing graph properties. Random Struct. Alg. 23 2357.CrossRefGoogle Scholar
[19] Hoppen, C., Kohayakawa, Y. and Sampaio, R. M. (2012) A note on permutation regularity. Discrete Appl. Math. 160 27162727.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 93113.Google Scholar
[21] Hoppen, C., Kohayakawa, Y., Moreira, C. G. and Sampaio, R. M. (2011) Testing permutation properties through subpermutations. Theoret. Comput. Sci. 412 35553567.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. 250255.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 264273.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 153160.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 252271.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 99121.Google Scholar
[30] Vaidya, P. (1989) Geometry helps in matching. SIAM J. Comput. 18 12011225.Google Scholar