Revised: August 18, 2018

Published: April 22, 2019

**Keywords:**property testing, boolean functions, monotonicity, learning

**Categories:**complexity theory, property testing, boolean functions, monotonicity, learning, Fourier analysis

**ACM Classification:**F.2, G.2

**AMS Classification:**68Q32, 68W20, 68Q25, 68Q17

**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).

----------