Testing permutation properties through subpermutations
From MaRDI portal
Publication:551179
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
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