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

DOI

10.1137/18M1217978

Document Type

Journal Article

Publication Date

1-1-2019

Publication Title

SIAM Journal on Discrete Mathematics

Volume

33

Issue

4

First Page

2111

Last Page

2125

ISSN

8954801

Keywords

Hypercube, Lower bounds, One sided, Property testing

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 gener alization of monotonicity. Recently, Canonne et al. [Innovations in Theoretical Computer Science, Schloss-Dagstuhl-Leibniz-Zentrum für Informatik GmBH, Wadern, Germany, 2017, 29] initiate the study of k-monotone functions in the area of property testing, and Newman et al. [SODA, SIAM, Philadelphia, 2017, pp. 1582-1597] 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, Ron, and Rubinfeld [J. Comput. System Sci., 72(2006), pp. 1012-1042]. In this process we show strong lower bounds on testing k-monotonicity. Specifically, we show that testing 2-monotonicity on the hypercube nonadaptively with one-sided error requires an exponential in ?n number of queries. This behavior shows a stark contrast with testing (1-)monotonicity, which only needs Õ (?n) queries. Furthermore, even the apparently eas ier task of distinguishing 2-monotone functions from functions that are far from being n·01-monotone also requires an exponential number of queries.

Open Access

Green Accepted

Link to Full Text

Share

COinS