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 (16)

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

This page was built for publication: Testing permutation properties through subpermutations