{"ID":2850154,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22845","arxiv_id":"2510.22845","title":"Testing forbidden order-pattern properties on hypergrids","abstract":"We study testing $π$-freeness of functions $f:[n]^d\\to\\mathbb{R}$, where $f$ is $π$-free if there there are no $k$ indices $x_1\\prec\\cdots\\prec x_k\\in [n]^d$ such that $f(x_i)\u003cf(x_j)$ and $π(i) \u003c π(j)$ for all $i,j \\in [k]$, where $\\prec$ is the natural partial order over $[n]^d$. Given $ε\\in(0,1)$, $ε$-testing $π$-freeness asks to distinguish $π$-free functions from those which are $ε$-far -- meaning at least $εn^d$ function values must be modified to make it $π$-free. While $k=2$ coincides with monotonicity testing, far less is known for $k\u003e2$. We initiate a systematic study of pattern freeness on higher-dimensional grids. For $d=2$ and all permutations of size $k=3$, we design an adaptive one-sided tester with query complexity $O(n^{4/5+o(1)})$. We also prove general lower bounds for $k=3$: every nonadaptive tester requires $Ω(n)$ queries, and every adaptive tester requires $Ω(\\sqrt{n})$ queries, yielding the first super-logarithmic lower bounds for $π$-freeness. For the monotone patterns $π=(1,2,3)$ and $(3,2,1)$, we present a nonadaptive tester with polylogarithmic query complexity, giving an exponential separation between monotone and nonmonotone patterns (unlike the one-dimensional case). A key ingredient in our $π$-freeness testers is new erasure-resilient ($δ$-ER) $ε$-testers for monotonicity over $[n]^d$ with query complexity $O(\\log^{O(d)}n/(ε(1-δ)))$, where $0\u003cδ\u003c1$ is an upper bound on the fraction of erasures. Prior ER testers worked only for $δ=O(ε/d)$. Our nonadaptive monotonicity tester is nearly optimal via a matching lower bound due to Pallavoor, Raskhodnikova, and Waingarten (Random Struct. Algorithms, 2022). Finally, we show that current techniques cannot yield sublinear-query testers for patterns of length $4$ even on two-dimensional hypergrids.","short_abstract":"We study testing $π$-freeness of functions $f:[n]^d\\to\\mathbb{R}$, where $f$ is $π$-free if there there are no $k$ indices $x_1\\prec\\cdots\\prec x_k\\in [n]^d$ such that $f(x_i)\u003cf(x_j)$ and $π(i) \u003c π(j)$ for all $i,j \\in [k]$, where $\\prec$ is the natural partial order over $[n]^d$. Given $ε\\in(0,1)$, $ε$-testing $π$-fre...","url_abs":"https://arxiv.org/abs/2510.22845","url_pdf":"https://arxiv.org/pdf/2510.22845v1","authors":"[\"Harish Chandramouleeswaran\",\"Ilan Newman\",\"Tomer Pelleg\",\"Nithin Varma\"]","published":"2025-10-26T21:27:12Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}