Fast property testing and metrics for permutations

DOI10.1017/S096354831800024XMaRDI QIDQ3177362zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Fan Wei

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.01270

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Randomized algorithms (68W20)

Abstract: The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are $epsilon$-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 $epsilon$ 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. Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in $1/epsilon$ 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.

Recommendations

• Permutation Property Testing under Different Metrics with Low Query Complexity
• Hereditary properties of permutations are strongly testable
• Every hereditary permutation property is testable
• Property testing and parameter testing for permutations
• Testing permutation properties through subpermutations

Cites work

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A note on permutation regularity
• A permutation regularity lemma
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Bounds for graph regularity and removal lemmas
• Davenport-Schinzel theory of matrices
• Easily testable graph properties
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Geometry Helps in Matching
• Graph removal lemmas
• Hereditary properties of permutations are strongly testable
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 3584785 (Why is no real title available?)
• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Large networks and graph limits
• Limits of permutation sequences
• Monotonic Subsequences
• On regularity lemmas and their algorithmic applications
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing permutation properties through subpermutations
• Testing subgraphs in large graphs
• The earth mover's distance as a metric for image retrieval
• Three theorems regarding testing graph properties

Cited in

(12)

• Every hereditary permutation property is testable
• Permutation Property Testing under Different Metrics with Low Query Complexity
• scientific article; zbMATH DE number 7283890 (Why is no real title available?)
• Hereditary properties of permutations are strongly testable
• Property testing and parameter testing for permutations
• Testing permutation properties through subpermutations
• Testability in group theory
• Strongly sublinear algorithms for testing pattern freeness
• On pattern-avoiding permutons
• Combinatorial reduction of set functions and matroid permutations through minor invertible product assignment
• Posets are easily testable
• A polynomial removal lemma for posets (extended abstract)

Describes a project that uses

Uses Software

• EMD

This page was built for publication: Fast property testing and metrics for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177362)