Testing permutation properties through subpermutations

DOI10.1016/j.tcs.2011.03.002zbMath1223.68078arXiv1106.1663OpenAlexW1986644892WikidataQ105583769 ScholiaQ105583769MaRDI QIDQ551179

Yoshiharu Kohayakawa, Carlos Hoppen, Carlos Gustavo T.de A. Moreira, Rudini Menezes Sampaio

Publication date: 14 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

permutationsproperty testingparameter testing

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05)

Related Items

Quasirandom permutations are characterized by 4-point densities, Fast Property Testing and Metrics for Permutations, Densities in large permutations and parameter testing, Patterns in random permutations, Unnamed Item, Finitely forcible graphons and permutons, Limits of \(k\)-dimensional poset sequences, Unnamed Item, Limits of structures and the example of tree semi-lattices, A note on permutation regularity, Quasi-random words and limits of word sequences, Independence of permutation limits at infinitely many scales, Weak regularity and finitely forcible graph limits, Higher-order fluctuations in dense random graph models, Poset limits can be totally ordered, Density maximizers of layered permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing properties of graphs and functions
• A permutation regularity lemma
• Limits of dense graph sequences
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• The complexity of the weight problem for permutation and matrix groups.
• On graphs with small subgraphs of large chromatic number
• Spot-checkers
• Quasirandom permutations
• The diameter of a scale-free random graph
• Limits of permutation sequences
• Regular Languages are Testable with a Constant Number of Queries
• Graph limits and parameter testing
• Quantum Property Testing
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Sublinear algorithms for testing monotone and unimodal distributions
• A sublinear algorithm for weakly approximating edit distance
• Every Monotone Graph Property Is Testable
• Three theorems regarding testing graph properties
• Testing satisfiability
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Quasi-random graphs
• Efficient testing of large graphs