2026-08-15T09:16:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8158 2024-03-06T10:39:19Z ddc:004 open_access

Testing k-Monotonicity Canonne, Clément L. Grigorescu, Elena Guo, Siyao Kumar, Akash Wimmer, Karl Boolean Functions Learning Monotonicity Property Testing A Boolean k-monotone function defined over a finite poset domain D alternates between the values 0 and 1 at most k times on any ascending chain in 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 >= 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 2^{O(\sqrt d . \log d . \log{1/\eps})} queries, while learning k-monotone functions requires 2^{\Omega(k . \sqrt d .{1/\eps})} queries (Blais et al. (RANDOM 2015)). 3. We present a tolerant test for functions f\colon[n]^d\to \{0,1\}$with complexity independent of n, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Elena Grigorescu and Siyao Guo and Akash Kumar and Karl Wimmer 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.29 urn:nbn:de:0030-drops-81583 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.29 eng https://creativecommons.org/licenses/by/3.0/legalcode