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 : https://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.