Strongly Sublinear Algorithms for Testing Pattern Freeness
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910556199321600 |
|---|---|
| author | Newman, Ilan Varma, Nithin |
| author_facet | Newman, Ilan Varma, Nithin |
| contents | For a permutation $π:[k] \to [k]$, a function $f:[n] \to \mathbb{R}$ contains a $π$-appearance if there exists $1 \leq i_1 < i_2 < \dots < i_k \leq n$ such that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ if and only if $π(s) < π(t)$. The function is $π$-free if it has no $π$-appearances. In this paper, we investigate the problem of testing whether an input function $f$ is $π$-free or whether $f$ differs on at least $\varepsilon n$ values from every $π$-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler (Random Structures and Algorithms 2019). We show that for all constants $k \in \mathbb{N}$, $\varepsilon \in (0,1)$, and permutation $π:[k] \to [k]$, there is a one-sided error $\varepsilon$-testing algorithm for $π$-freeness of functions $f:[n] \to \mathbb{R}$ that makes $\tilde{O}(n^{o(1)})$ queries. We improve significantly upon the previous best upper bound $O(n^{1 - 1/(k-1)})$ by Ben-Eliezer and Canonne (SODA 2018). Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2106_04856 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Strongly Sublinear Algorithms for Testing Pattern Freeness Newman, Ilan Varma, Nithin Data Structures and Algorithms 68W20, 68W25 F.2 For a permutation $π:[k] \to [k]$, a function $f:[n] \to \mathbb{R}$ contains a $π$-appearance if there exists $1 \leq i_1 < i_2 < \dots < i_k \leq n$ such that for all $s,t \in [k]$, $f(i_s) < f(i_t)$ if and only if $π(s) < π(t)$. The function is $π$-free if it has no $π$-appearances. In this paper, we investigate the problem of testing whether an input function $f$ is $π$-free or whether $f$ differs on at least $\varepsilon n$ values from every $π$-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler (Random Structures and Algorithms 2019). We show that for all constants $k \in \mathbb{N}$, $\varepsilon \in (0,1)$, and permutation $π:[k] \to [k]$, there is a one-sided error $\varepsilon$-testing algorithm for $π$-freeness of functions $f:[n] \to \mathbb{R}$ that makes $\tilde{O}(n^{o(1)})$ queries. We improve significantly upon the previous best upper bound $O(n^{1 - 1/(k-1)})$ by Ben-Eliezer and Canonne (SODA 2018). Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms. |
| title | Strongly Sublinear Algorithms for Testing Pattern Freeness |
| topic | Data Structures and Algorithms 68W20, 68W25 F.2 |
| url | https://arxiv.org/abs/2106.04856 |