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 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 pol y ( n k ) queries. In this work we disprove the conjecture, and show that even 2 -monotonicity requires an exponential in 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.