An optimal lower bound for monotonicity testing over hypergrids

DOI10.1007/978-3-642-40328-6_30MaRDI QIDQ2851875zbMATH OpenOpenAlexFDO

Authors Deeparnab Chakrabarty, C. Seshadhri

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

zbMATH Keywords

hypergridslower boundsmonotonicity testingsublinear algorithms

Mathematics Subject Classification ID

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

Abstract: For positive integers $n,d$, consider the hypergrid $[n{]}^d$ with the coordinate-wise product partial ordering denoted by $prec$. A function $f:[n{]}^{d}mapstomathbbN$ is monotone if $forallxprecy$, $f(x)leqf(y)$. A function $f$ is $eps$-far from monotone if at least an $eps$-fraction of values must be changed to make $f$ monotone. Given a parameter $eps$, a emph{monotonicity tester} must distinguish with high probability a monotone function from one that is $eps$-far. We prove that any (adaptive, two-sided) monotonicity tester for functions $f:[n{]}^{d}mapstomathbbN$ must make $Omega(ep{s}^{-1}dlogn-ep{s}^{-1}logep{s}^{-1})$ queries. Recent upper bounds show the existence of $O(ep{s}^{-1}dlogn)$ query monotonicity testers for hypergrids. This closes the question of monotonicity testing for hypergrids over arbitrary ranges. The previous best lower bound for general hypergrids was a non-adaptive bound of $Omega(dlogn)$.

Recommendations

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

Cited in

(12)

• Testing monotonicity over graph products
• Monotonicity testing and shortest-path routing on the cube
• Monotonicity testing and shortest-path routing on the cube
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Testing hereditary properties of sequences
• Adaptive lower bound for testing monotonicity on the line
• Automata, Languages and Programming
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Improved algorithm for permutation testing

This page was built for publication: An optimal lower bound for monotonicity testing over hypergrids

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