{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T09:38:45Z","timestamp":1773049125148,"version":"3.50.1"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T00:00:00Z","timestamp":1527120000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are \u03b5-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 \u2018constant\u2019 query complexity, depending only on \u03b5 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.<\/jats:p><jats:p>Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1\/\u03b5 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.<\/jats:p>","DOI":"10.1017\/s096354831800024x","type":"journal-article","created":{"date-parts":[[2018,5,24]],"date-time":"2018-05-24T13:30:44Z","timestamp":1527168644000},"page":"539-579","source":"Crossref","is-referenced-by-count":5,"title":["Fast Property Testing and Metrics for Permutations"],"prefix":"10.1017","volume":"27","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FAN","family":"WEI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2018,5,24]]},"reference":[{"key":"S096354831800024X_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0218080"},{"key":"S096354831800024X_ref29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"S096354831800024X_ref27","unstructured":"Monge G. (1781), M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. Histoire de l'Acad\u00e9mie Royale des Sciences de Paris, pp. 666\u2013704."},{"key":"S096354831800024X_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"S096354831800024X_ref24","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1953-0053256-2"},{"key":"S096354831800024X_ref23","doi-asserted-by":"crossref","unstructured":"Klimo\u0161ov\u00e1 T. and Kr\u00e1l' D. (2012) Hereditary properties of permutations are strongly testable. arXiv:1208.2624 An early version appeared in SODA '14: 25th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, ACM (2014), pp. 1164\u20131173.","DOI":"10.1137\/1.9781611973402.86"},{"key":"S096354831800024X_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04166-6_22"},{"key":"S096354831800024X_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.09.003"},{"key":"S096354831800024X_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"S096354831800024X_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90316-8"},{"key":"S096354831800024X_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.03.002"},{"key":"S096354831800024X_ref15","unstructured":"Fox J. and Wei F. Strongly testing hereditary permutation properties with polynomial query complexity. In preparation."},{"key":"S096354831800024X_ref11","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s","year":"1935","journal-title":"Compositio Math."},{"key":"S096354831800024X_ref8","unstructured":"Diaconis P. personal communication."},{"key":"S096354831800024X_ref7","doi-asserted-by":"crossref","first-page":"R22","DOI":"10.37236\/1048","article-title":"A permutation regularity lemma","volume":"13","author":"Cooper","year":"2006","journal-title":"Electron. J. Combin."},{"key":"S096354831800024X_ref6","first-page":"1","volume-title":"Surveys in Combinatorics 2013","author":"Conlon","year":"2013"},{"key":"S096354831800024X_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-012-0171-x"},{"key":"S096354831800024X_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306007759"},{"key":"S096354831800024X_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"S096354831800024X_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"S096354831800024X_ref25","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz L. (2012) Large Networks and Graph Limits, Vol. 60 of American Mathematical Society Colloquium Publications, AMS.","DOI":"10.1090\/coll\/060"},{"key":"S096354831800024X_ref12","unstructured":"Fox J. Stanley\u2013Wilf limits are typically exponential. Adv. Math., to appear."},{"key":"S096354831800024X_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.06.002"},{"key":"S096354831800024X_ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"S096354831800024X_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000049"},{"key":"S096354831800024X_ref9","doi-asserted-by":"crossref","unstructured":"Diaconis P. (1988) Group Representations in Probability and Statistics, Vol. 11 of Lecture Notes Monograph Series, Institute of Mathematical Statistics.","DOI":"10.1214\/lnms\/1215467407"},{"key":"S096354831800024X_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000765"},{"key":"S096354831800024X_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S096354831800024X_ref10","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1111\/j.2517-6161.1977.tb01624.x","article-title":"Spearman's footrule as a measure of disarray","volume":"39","author":"Diaconis","year":"1977","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"S096354831800024X_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.09.037"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831800024X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,6]],"date-time":"2024-07-06T23:48:50Z","timestamp":1720309730000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831800024X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,24]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S096354831800024X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831800024x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,24]]}}}