Fast Property Testing and Metrics for Permutations

DOI10.1017/S096354831800024XzbMath1484.68323arXiv1611.01270OpenAlexW2963363569MaRDI QIDQ3177362

Fan Wei, Jacob Fox

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) Randomized algorithms (68W20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing permutation properties through subpermutations
• Excluded permutation matrices and the Stanley-Wilf conjecture
• A permutation regularity lemma
• Davenport-Schinzel theory of matrices
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• The earth mover's distance as a metric for image retrieval
• Bounds for graph regularity and removal lemmas
• Limits of permutation sequences
• Graph removal lemmas
• Geometry Helps in Matching
• Property testing and its connection to learning and approximation
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Three theorems regarding testing graph properties
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Easily Testable Graph Properties
• On Regularity Lemmas and their Algorithmic Applications
• Hereditary properties of permutations are strongly testable
• Monotonic Subsequences
• A note on permutation regularity

This page was built for publication: Fast Property Testing and Metrics for Permutations