An Optimal Lower Bound for Monotonicity Testing over Hypergrids

DOI10.1007/978-3-642-40328-6_30zbMath1405.68127arXiv1304.5264OpenAlexW2951610245MaRDI QIDQ2851875

C. Seshadhri, Deeparnab Chakrabarty

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

lower boundssublinear algorithmsmonotonicity testinghypergrids

Mathematics Subject Classification ID

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

Related Items (3)

On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Improved algorithm for permutation testing ⋮ Unnamed Item

This page was built for publication: An Optimal Lower Bound for Monotonicity Testing over Hypergrids