[sans titre]

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

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.