Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

DOI10.1145/2488608.2488661zbMath1293.90055arXiv1204.0849OpenAlexW2963845289MaRDI QIDQ5495812

Deeparnab Chakrabarty, C. Seshadhri

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

monotonicityhypercubesproperty testinghypergridsLipschitz testing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

Testing Lipschitz functions on hypergrid domains ⋮ Parameterized property testing of functions ⋮ On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Unnamed Item ⋮ Is submodularity testable? ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ A non-extendibility certificate for submodularity and applications ⋮ Unnamed Item ⋮ An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

This page was built for publication: Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids