License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.98
URN: urn:nbn:de:0030-drops-164390
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16439/
Go to the corresponding LIPIcs Volume Portal

Newman, Ilan ; Varma, Nithin

Strongly Sublinear Algorithms for Testing Pattern Freeness

pdf-format:
LIPIcs-ICALP-2022-98.pdf (0.8 MB)

Abstract

For a permutation π:[k] → [k], a function f:[n] → ℝ contains a π-appearance if there exists 1 ≤ i₁ < i₂ < … < i_k ≤ n such that for all s,t ∈ [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 ε 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 [Ilan Newman et al., 2019]. We show that for all constants k ∈ ℕ, ε ∈ (0,1), and permutation π:[k] → [k], there is a one-sided error ε-testing algorithm for π-freeness of functions f:[n] → ℝ that makes Õ(n^o(1)) queries. We improve significantly upon the previous best upper bound O(n^{1 - 1/(k-1)}) by Ben-Eliezer and Canonne [Omri Ben-Eliezer and Clément L. Canonne, 2018]. Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms.

BibTeX - Entry

@InProceedings{newman_et_al:LIPIcs.ICALP.2022.98,
  author =	{Newman, Ilan and Varma, Nithin},
  title =	{{Strongly Sublinear Algorithms for Testing Pattern Freeness}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{98:1--98:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16439},
  URN =		{urn:nbn:de:0030-drops-164390},
  doi =		{10.4230/LIPIcs.ICALP.2022.98},
  annote =	{Keywords: Property testing, Pattern freeness, Sublinear algorithms}
}

Keywords: Property testing, Pattern freeness, Sublinear algorithms
Collection: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Issue Date: 2022
Date of publication: 28.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI