Approximating the distance to monotonicity in high dimensions

DOI10.1145/1798596.1798605zbMath1300.68066OpenAlexW1992650621MaRDI QIDQ2930335

Dana Ron, Shahar Fattal

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

monotonicityproperty testingsublinear approximation algorithmsdistance approximation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Is submodularity testable? ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Local Property Reconstruction and Monotonicity ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

This page was built for publication: Approximating the distance to monotonicity in high dimensions