License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.40
URN: urn:nbn:de:0030-drops-94448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9444/
Grigorescu, Elena ;
Kumar, Akash ;
Wimmer, Karl
Flipping out with Many Flips: Hardness of Testing k-Monotonicity
Abstract
A function f:{0,1}^n - > {0,1} is said to be k-monotone 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 k-monotone functions in the area of property testing, and Newman et al. (SODA 2017) study testability of families characterized by freeness from order patterns on real-valued functions over the line [n] domain.
We study k-monotone 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 2-monotonicity on the hypercube non-adaptively with one-sided 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 2-monotone 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 k-monotone 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 k-Monotonicity}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {40:1--40:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9444},
URN = {urn:nbn:de:0030-drops-94448},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.40},
annote = {Keywords: Property Testing, Boolean Functions, k-Monotonicity, Lower Bounds}
}
|
Keywords: |
|
Property Testing, Boolean Functions, k-Monotonicity, Lower Bounds |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
13.08.2018 |
