Permutation Property Testing under Different Metrics with Low Query Complexity

DOI10.1137/1.9781611974782.107MaRDI QIDQ4575850zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Fan Wei

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.107

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Fast property testing and metrics for permutations
• Property testing and parameter testing for permutations
• Publication:4860267
• Testing permutation properties through subpermutations
• On the number of queries necessary to identify a permutation
• A unified approach to permutation testing for equivalence
• Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
• The query complexity of finding a hidden permutation
• Tests for permutation functions
• scientific article; zbMATH DE number 1241385

Cited in

(7)

• Every hereditary permutation property is testable
• Fast property testing and metrics for permutations
• Improved bounds for testing forbidden order patterns
• Hereditary properties of permutations are strongly testable
• Property testing and parameter testing for permutations
• Testing permutation properties through subpermutations
• On pattern-avoiding permutons

This page was built for publication: Permutation Property Testing under Different Metrics with Low Query Complexity

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