Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error

DOI10.1145/3512750MaRDI QIDQ5868886zbMATH OpenOpenAlexWikidataFDO

Authors Dana Ron, Asaf Rosin

Publication date 24 September 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3512750

zbMATH Keywords

property testingsubsequence freeness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Algorithms on strings (68W32)

Recommendations

• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• scientific article; zbMATH DE number 3915459
• scientific article; zbMATH DE number 6881150
• On distribution-free tests for one-sample location problem based on subsample exterma
• Asymptotically optimal sequential hypothesis testing
• Sample-size-optimal sequential testing
• Nearly minimax one-sided mixture-based sequential tests
• Distribution-free tests of subhypotheses

Cited in

(4)

• Polynomial removal lemmas for ordered graphs
• Sample-based distance-approximation for subsequence-freeness
• Distribution-free proofs of proximity
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)

This page was built for publication: Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error

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