Testing local properties of arrays

DOI10.4230/LIPICS.ITCS.2019.11MaRDI QIDQ6309907arXivFDO

Authors Omri Ben-Eliezer

Publication date 18 November 2018

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2019.11

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n{]}^{d}oSigma$ is $k$-local if it can be defined by a family of $kimesldotsimesk$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and submodularity are $2$-local; convexity is (usually) $3$-local; and many typical problems in computational biology and computer vision involve $o(n)$-local properties. In this work, we present a generic approach to test all local properties of arrays over any finite (and not necessarily bounded size) alphabet. We show that any $k$-local property of $d$-dimensional arrays is testable by a simple canonical one-sided error non-adaptive $varepsilon$-test, whose query complexity is $O(epsilo{n}^{-1}klogfracepsilonnk)$ for $d=1$ and $O(c_{d}epsilo{n}^{-1/d}kcdot{n}^{d-1})$ for $d>1$. The queries made by the canonical test constitute sphere-like structures of varying sizes, and are completely independent of the property and the alphabet $Sigma$. The query complexity is optimal for a wide range of parameters: For $d=1$, this matches the query complexity of many previously investigated local properties, while for $d>1$ we design and analyze new constructions of $k$-local properties whose one-sided non-adaptive query complexity matches our upper bounds. For some previously studied properties, our method provides the first known sublinear upper bound on the query complexity.

This page was built for publication: Testing local properties of arrays

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