Estimating the distance to a monotone function

DOI10.1002/rsa.20167zbMath1161.68051OpenAlexW1528180898MaRDI QIDQ5433267

Nir Ailon, Ding Liu, Seshadhri Comandur, Bernard Chazelle

Publication date: 8 January 2008

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20167

zbMATH Keywords

monotone functionsproperty testingsublinear algorithmsdistance estimationtolerant property testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05) Randomized algorithms (68W20)

Related Items

Testing Lipschitz functions on hypergrid domains, On Monotonicity Testing and Boolean Isoperimetric-type Theorems, On the monotonicity of a data stream, Approximating the distance to monotonicity of Boolean functions, Improved algorithm for permutation testing, Erasure-Resilient Property Testing, Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, Estimating the Longest Increasing Sequence in Polylogarithmic Time, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Local Property Reconstruction and Monotonicity, Unnamed Item, A linear fit gets the correct monotonicity directions

Cites Work

• Information theory in property testing and monotonicity testing in higher dimension
• Unnamed Item