Revised: August 18, 2018
Published: April 22, 2019
Abstract: [Plain Text Version]
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.
- We demonstrate a separation between testing $k$-monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$;
- 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));
- We present a tolerant test for $k$-monotonicity of functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$. The test implies a tolerant test for monotonicity of functions $f\colon[n]^d\to [0,1]$ in $\ell_1$ distance, which makes progress on a problem left open by Berman et al. (STOC 2014).
----------
Licensed under a Creative Commons Attribution License (CC-BY)