Improved algorithm for permutation testing

DOI10.1016/j.tcs.2023.114316arXiv2006.08473OpenAlexW4388948151MaRDI QIDQ6138826

No author found.

Publication date: 16 January 2024

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

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

zbMATH Keywords

property testingpermutation testing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Monotonicity testing and shortest-path routing on the cube
• Property testing lower bounds via communication complexity
• Spot-checkers
• On the strength of comparisons in property testing
• Tolerant property testing and distance approximation
• An Optimal Lower Bound for Monotonicity Testing over Hypergrids
• Testing for Forbidden Order Patterns in an Array
• Improved Bounds for Testing Forbidden Order Patterns
• Parameterized Property Testing of Functions
• Adaptive Lower Bound for Testing Monotonicity on the Line
• Finding small patterns in permutations in linear time
• Estimating the distance to a monotone function
• Estimating the Longest Increasing Sequence in Polylogarithmic Time

This page was built for publication: Improved algorithm for permutation testing