Canonne, Clément L. ;
Grigorescu, Elena ;
Guo, Siyao ;
Kumar, Akash ;
Wimmer, Karl
Testing kMonotonicity
Abstract
A Boolean kmonotone 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, kmonotone functions are natural generalizations of the classical monotone functions, which are the 1monotone functions.
Motivated by the recent interest in kmonotone 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 kmonotone functions, in the property testing model. In this model, the goal is to distinguish functions that are kmonotone (or are close to being kmonotone) from functions that are far from being kmonotone.
Our results include the following:
1. We demonstrate a separation between testing kmonotonicity 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 kmonotonicity can be performed with 2^{O(\sqrt d . \log d . \log{1/\eps})} queries, while learning kmonotone 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 testingbylearning paradigm, use novel applications of Fourier analysis on the grid [n]^d, and draw connections to distribution testing techniques.
Our techniques exploit the testingbylearning paradigm, use novel applications of Fourier analysis on the grid [n]^d, and draw connections to distribution testing techniques.
BibTeX  Entry
@InProceedings{canonne_et_al:LIPIcs:2017:8158,
author = {Cl{\'e}ment L. Canonne and Elena Grigorescu and Siyao Guo and Akash Kumar and Karl Wimmer},
title = {{Testing kMonotonicity}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {29:129:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8158},
URN = {urn:nbn:de:0030drops81583},
doi = {10.4230/LIPIcs.ITCS.2017.29},
annote = {Keywords: Boolean Functions, Learning, Monotonicity, Property Testing}
}
2017
Keywords: 

Boolean Functions, Learning, Monotonicity, Property Testing 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

2017 