DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.27

Almost Optimal Distribution-Free Sample-Based Testing of k-Modality

Authors: Dana Ron and Asaf Rosin

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

For an integer k ≥ 0, a sequence σ = σ₁,… ,σ_n over a fully ordered set is k-modal, if there exist indices 1 = a₀ < a₁ < … < a_{k+1} = n such that for each i, the subsequence σ_{a_i},… ,σ_{a_{i+1}} is either monotonically non-decreasing or monotonically non-increasing. The property of k-modality is a natural extension of monotonicity, which has been studied extensively in the area of property testing. We study one-sided error property testing of k-modality in the distribution-free sample-based model. We prove an upper bound of O({√{kn}log k}/ε) on the sample complexity, and an almost matching lower bound of Ω(√{kn}/ε). When the underlying distribution is uniform, we obtain a completely tight bound of Θ(√{kn/ε}), which generalizes what is known for sample-based testing of monotonicity under the uniform distribution.

Cite as

Dana Ron and Asaf Rosin. Almost Optimal Distribution-Free Sample-Based Testing of k-Modality. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ron_et_al:LIPIcs.APPROX/RANDOM.2020.27,
  author =	{Ron, Dana and Rosin, Asaf},
  title =	{{Almost Optimal Distribution-Free Sample-Based Testing of k-Modality}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.27},
  URN =		{urn:nbn:de:0030-drops-126307},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.27},
  annote =	{Keywords: Sample-based property testing, Distribution-free property testing, k-modality}
}

Search Results

Documents authored by Rosin, Asaf

Almost Optimal Distribution-Free Sample-Based Testing of k-Modality

Abstract

Cite as

Thanks for your feedback!

Could not send message