EUVIMEDEUVIMED entdecken
Crossref

Strongly Sublinear Algorithms for Testing Pattern Freeness

Ilan Newman, Nithin Varma

TheoretiCS · 2024

DOI: 10.46298/theoretics.24.1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von Ilan Newman und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a permutation $\pi:[k] \to [k]$, a function $f:[n] \to \mathbb{R}$ contains a $\pi$-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 $\pi(s) < \pi(t)$. The function is $\pi$-free if it has no $\pi$-appearances. In this paper, we investigate the problem of testing whether an input function $f$ is $\pi$-free or whether $f$ differs on at least $\varepsilon n$ values from every $\pi$-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 $\pi:[k] \to [k]$, there is a one-sided error $\varepsilon$-testing algorithm for $\pi$-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.

Zitieren

APA

Newman, I., & Varma, N. (2024). Strongly Sublinear Algorithms for Testing Pattern Freeness. TheoretiCS. https://doi.org/10.46298/theoretics.24.1

Vancouver

Newman I, Varma N. Strongly Sublinear Algorithms for Testing Pattern Freeness. TheoretiCS. 2024. doi:10.46298/theoretics.24.1

BibTeX
@article{Newman2024,
  author = {Newman, Ilan and Varma, Nithin},
  title = {Strongly Sublinear Algorithms for Testing Pattern Freeness},
  journal = {TheoretiCS},
  year = {2024},
  doi = {10.46298/theoretics.24.1}
}
Kostenlos starten →