Theory of Computing
-------------------
Title : Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions
Authors : Clement L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer
Volume : 15
Number : 1
Pages : 1-55
URL : http://www.theoryofcomputing.org/articles/v015a001
Abstract
--------
A Boolean _$k$-monotone_ function defined over a finite poset domain
$\mathcal{D}$ alternates between the values $0$ and $1$ at most $k$
times on any ascending chain in $\mathcal{D}$. Therefore, $k$-monotone
functions are natural generalizations of the classical _monotone_
functions, which are the _$1$-monotone_ functions.
Motivated by the recent interest in $k$-monotone functions in the
context of circuit complexity and learning theory, and by the central
role that monotonicity testing plays in the context of property
testing, we initiate a systematic study of $k$-monotone functions, in
the property testing model. In this model, the goal is to distinguish
functions that are $k$-monotone (or are close to being $k$-monotone)
from functions that are far from being $k$-monotone.
Our results include the following:
1. We demonstrate a separation between testing $k$-monotonicity and
testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$;
2. We demonstrate a separation between testing and learning on $\{0,1\}^d$,
for $k=\omega(\log d)$: testing $k$-monotonicity can be performed with
$\exp(O(\sqrt d \cdot \log d\cdot \log(1/\eps)))$ queries, while learning
$k$-monotone functions requires $\exp(\Omega(k\cdot\sqrt d\cdot{1/\eps}))$
queries (Blais et al. (RANDOM 2015));
3. We present a tolerant test for $k$-monotonicity of functions
$f : [n]^d\to \{0,1\}$ with complexity independent of $n$. The test
implies a tolerant test for monotonicity of functions $f : [n]^d\to [0,1]$
in $\ell_1$ distance, which makes progress on a problem left open by
Berman et al. (STOC 2014). Our techniques exploit the testing-by-learning
paradigm, use novel applications of Fourier analysis on the grid $[n]^d$,
and draw connections to distribution testing techniques.
Our techniques exploit the testing-by-learning paradigm, use novel
applications of Fourier analysis on the grid [n]^d, and draw connections
to distribution testing techniques.
------
An extended abstract of this paper appeared in the Proceedings of the
8th Innovations in Theoretical Computer Science conference, 2017.