Grigorescu, Elena ;
Kumar, Akash ;
Wimmer, Karl
Flipping out with Many Flips: Hardness of Testing kMonotonicity
Abstract
A function f:{0,1}^n  > {0,1} is said to be kmonotone if it flips between 0 and 1 at most k times on every ascending chain. Such functions represent a natural generalization of (1)monotone functions, and have been recently studied in circuit complexity, PAC learning, and cryptography. Our work is part of a renewed focus in understanding testability of properties characterized by freeness of arbitrary order patterns as a generalization of monotonicity. Recently, Canonne et al. (ITCS 2017) initiate the study of kmonotone functions in the area of property testing, and Newman et al. (SODA 2017) study testability of families characterized by freeness from order patterns on realvalued functions over the line [n] domain.
We study kmonotone functions in the more relaxed parametrized property testing model, introduced by Parnas et al. (JCSS, 72(6), 2006). In this process we resolve a problem left open in previous work. Specifically, our results include the following.
1) Testing 2monotonicity on the hypercube nonadaptively with onesided error requires an exponential in sqrt{n} number of queries. This behavior shows a stark contrast with testing (1)monotonicity, which only needs O~(sqrt{n}) queries (Khot et al. (FOCS 2015)). Furthermore, even the apparently easier task of distinguishing 2monotone functions from functions that are far from being n^{.01}monotone also requires an exponential number of queries.
2) On the hypercube [n]^d domain, there exists a testing algorithm that makes a constant number of queries and distinguishes functions that are kmonotone from functions that are far from being O(kd^2) monotone. Such a dependency is likely necessary, given the lower bound above for the hypercube.
BibTeX  Entry
@InProceedings{grigorescu_et_al:LIPIcs:2018:9444,
author = {Elena Grigorescu and Akash Kumar and Karl Wimmer},
title = {{Flipping out with Many Flips: Hardness of Testing kMonotonicity}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {40:140:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9444},
URN = {urn:nbn:de:0030drops94448},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.40},
annote = {Keywords: Property Testing, Boolean Functions, kMonotonicity, Lower Bounds}
}
13.08.2018
Keywords: 

Property Testing, Boolean Functions, kMonotonicity, Lower Bounds 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Issue date: 

2018 
Date of publication: 

13.08.2018 