Testing forbidden order-pattern properties on hypergrids

Given a permutation π : [k] → [k], a function f : [n] d → R is said to be π-free if there are no k indices x 1 ≺ • • • ≺ x k ∈ [n] d such that f (x i ) < f (x j ) and π(i) < π(j) for all i, j ∈ [k], where ≺ is the natural partial order over [n] d . For a fixed π and ǫ ∈ (0, 1), the problem of ǫ-testing π-freeness is to distinguish the case that f is π-free from the case that at least ǫn d values of f need to be modified in order to make it π-free. When k = 2, the problem is identical to monotonicity testing, which is extensively studied in property testing. The case of k > 2 has also received significant attention for functions f : [n] → R.

We initiate a systematic study of testing of π-freeness for higher dimensional grids; specifically, for permutations of size 3 over hypergrids of dimension 2. We design an adaptive one-sided error π-freeness tester with query complexity O(n 4/5+o(1) ) that works for all permutations of size 3. We then argue that for general permutations of size 3, every nonadaptive tester must have query complexity Ω(n), and further, that every adaptive tester must have query complexity Ω( √ n). This is the first general lower bound for testing π-freeness that is higher than Θ(log n).

For the important special case of π = (1, 2, 3) or (3, 2, 1), we design a nonadaptive tester with a significantly improved (nearly optimal) query complexity of polylog n. Such an exponential gap in the complexity of testing freeness of nonmonotone and monotone patterns is not known, in general, in the one-dimensional case.

Erasure-resilient (ER) monotonicity testers are important subroutines in the design of our π-freeness testers. We design δ-ER ǫ-testers for monotonicity for functions f : [n] d → R with query complexity O log O(d) n ǫ(1-δ)

, where δ ∈ (0, 1) is an upper bound on the fraction of erasures.

Earlier erasure-resilient monotonicity testers worked only when δ = O(ǫ/d). The complexity of our nonadaptive monotonicity tester is nearly optimal as evidenced by a lower bound of Pallavoor, Raskhodnikova, and Waingarten (Random Struct. Algorithms, 2022).

Lastly, we argue that the current techniques in function property testing cannot give us sublinear-query testers for patterns of length 4 even for 2-dimensional hypergrids.