Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.27
URN: urn:nbn:de:0030-drops-126307
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12630/
Ron, Dana ; Rosin, Asaf
Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{ron_et_al:LIPIcs:2020:12630,
author = {Dana Ron and Asaf Rosin},
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 = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12630},
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}
}
| Keywords: | Sample-based property testing, Distribution-free property testing, k-modality | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 11.08.2020 |
