Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids

DOI10.1145/2488608.2488661MaRDI QIDQ5495812zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, C. Seshadhri

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

hypercubeshypergridsLipschitz testingmonotonicityproperty testing

Mathematics Subject Classification ID

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

Abstract: The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic, well-studied, yet unsolved question in property testing. We are given query access to $f:[k{]}^{n}mapstoR$ (for some ordered range $R$). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by $prec$. A function is emph{monotone} if for all pairs $xprecy$, $f(x)leqf(y)$. The distance to monotonicity, $ep{s}_f$, is the minimum fraction of values of $f$ that need to be changed to make $f$ monotone. For $k=2$ (the boolean hypercube), the usual tester is the emph{edge tester}, which checks monotonicity on adjacent pairs of domain points. It is known that the edge tester using $O(ep{s}^{-1}nlog|R|)$ samples can distinguish a monotone function from one where $ep{s}_f>eps$. On the other hand, the best lower bound for monotonicity testing over the hypercube is $min(|R{|}^2,n)$. This leaves a quadratic gap in our knowledge, since $|R|$ can be $2^n$. We resolve this long standing open problem and prove that $O(n/eps)$ samples suffice for the edge tester. For hypergrids, known testers require $O(ep{s}^{-1}nlogklog|R|)$ samples, while the best known (non-adaptive) lower bound is $Omega(ep{s}^{-1}nlogk)$. We give a (non-adaptive) monotonicity tester for hypergrids running in $O(ep{s}^{-1}nlogk)$ time. Our techniques lead to optimal property testers (with the same running time) for the natural emph{Lipschitz property} on hypercubes and hypergrids. (A $c$-Lipschitz function is one where $|f(x)-f(y)|leqc|x-y{|}_1$.) In fact, we give a general unified proof for $O(ep{s}^{-1}nlogk)$-query testers for a class of "bounded-derivative" properties, a class containing both monotonicity and Lipschitz.

Recommendations

• An optimal lower bound for monotonicity testing over hypergrids
• scientific article; zbMATH DE number 6395191
• A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
• Testing Lipschitz functions on hypergrid domains
• Adaptive lower bound for testing monotonicity on the line

Cited in

(36)

• A non-extendibility certificate for submodularity and applications
• Testing Lipschitz functions on hypergrid domains
• An o(n) monotonicity tester for Boolean functions over the hypercube
• An optimal lower bound for monotonicity testing over hypergrids
• Testing Lipschitz functions on hypergrid domains
• Testing monotonicity over graph products
• Monotonicity testing and shortest-path routing on the cube
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Erasure-Resilient Property Testing
• Parameterized property testing of functions
• Testing k-monotonicity
• Is submodularity testable?
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Testing hereditary properties of sequences
• Adaptive lower bound for testing monotonicity on the line
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing local properties of arrays
• Optimal unateness testers for real-valued functions: adaptivity helps
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• L_p-testing
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Discrete and Computational Geometry
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Approximating the distance to monotonicity of Boolean functions
• scientific article; zbMATH DE number 7765404 (Why is no real title available?)
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• Strongly sublinear algorithms for testing pattern freeness
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Testing intersecting and union-closed families
• Property testing with online adversaries
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• Property testing with online adversaries
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Relative-error testing of conjunctions and decision lists

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

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