2026-07-23T19:20:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12630 2024-03-06T10:51:18Z ddc:004 open_access

Almost Optimal Distribution-Free Sample-Based Testing of k-Modality Ron, Dana Rosin, Asaf Sample-based property testing Distribution-free property testing k-modality 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dana Ron and Asaf Rosin 2020 Is Part Of LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2020.27 urn:nbn:de:0030-drops-126307 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.27 eng https://creativecommons.org/licenses/by/3.0/legalcode