Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-088 | 3rd June 2018 19:53

Flipping out with many flips: hardness of testing k-monotonicity

RSS-Feed




Revision #1
Authors: Elena Grigorescu, Akash Kumar, Karl Wimmer
Accepted on: 3rd June 2018 19:53
Downloads: 608
Keywords: 


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



Changes to previous version:

Added a bicriteria tester for the hypergrid


Paper:

TR17-088 | 10th May 2017 23:52

K-Monotonicity is Not Testable on the Hypercube





TR17-088
Authors: Elena Grigorescu, Akash Kumar, Karl Wimmer
Publication: 11th May 2017 18:52
Downloads: 952
Keywords: 


Abstract:

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates 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.

In property testing, the fact that $1$-monotonicity can be locally tested with $\poly n$ queries led to a previous conjecture that $k$-monotonicity can be tested with $poly(n^k)$ queries. In this work we disprove the conjecture, and show that even $2$-monotonicity requires an exponential in $\sqrt{n}$ number of queries. 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.

Our results follow from constructions of families that are hard for a canonical tester that picks a random chain and queries all points on it. Our techniques rely on a simple property of the violation graph and on probabilistic arguments necessary to understand chain tests.



ISSN 1433-8092 | Imprint