Volume 15 (2019) Article 1 pp. 1-55

Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions

by Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer

Received: March 10, 2017
Revised: August 18, 2018
Published: April 22, 2019

$\newcommand{\ensuremath}[1]{#1} \newcommand{\eps}{\ensuremath{\varepsilon}}$

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

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.

DOI: 10.4086/toc.2019.v015a001

© 2019 Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer
Licensed under a Creative Commons Attribution License (CC-BY)