pdf icon
Volume 15 (2019) Article 1 pp. 1-55
Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions
Received: March 10, 2017
Revised: August 18, 2018
Published: April 22, 2019
Download article from ToC site:
[PDF (508K)] [PS (3514K)] [Source ZIP]
Keywords: property testing, boolean functions, monotonicity, learning
ACM Classification: F.2, G.2
AMS Classification: 68Q32, 68W20, 68Q25, 68Q17

Abstract: [Plain Text Version]

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