Distribution-Free Property-Testing

DOI10.1137/050645804zbMath1156.68057OpenAlexW2064609684MaRDI QIDQ3519390

Shirley Halevy, Eyal Kushilevitz

Publication date: 14 August 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

monotonicity testinglow-degree testingdistribution-free property-testingdistribution-free testing lower boundsproperty-testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (7)

An optimal tester for \(k\)-linear ⋮ An optimal tester for \(k\)-Linear ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Almost Optimal Testers for Concise Representations. ⋮ Estimating the Longest Increasing Sequence in Polylogarithmic Time ⋮ Almost optimal distribution-free junta testing ⋮ Unnamed Item

This page was built for publication: Distribution-Free Property-Testing