2026-07-21T12:28:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21039 2024-09-16T06:02:39Z ddc:004 open_access

Support Testing in the Huge Object Model Adar, Tomer Fischer, Eldar Levi, Amit Huge-Object model Property Testing The Huge Object model is a distribution testing model in which we are given access to independent samples from an unknown distribution over the set of strings {0,1}ⁿ, but are only allowed to query a few bits from the samples. We investigate the problem of testing whether a distribution is supported on m elements in this model. It turns out that the behavior of this property is surprisingly intricate, especially when also considering the question of adaptivity. We prove lower and upper bounds for both adaptive and non-adaptive algorithms in the one-sided and two-sided error regime. Our bounds are tight when m is fixed to a constant (and the distance parameter ε is the only variable). For the general case, our bounds are at most O(log m) apart. In particular, our results show a surprising O(log ε^{-1}) gap between the number of queries required for non-adaptive testing as compared to adaptive testing. For one-sided error testing, we also show that an O(log m) gap between the number of samples and the number of queries is necessary. Our results utilize a wide variety of combinatorial and probabilistic methods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomer Adar and Eldar Fischer and Amit Levi 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.46 urn:nbn:de:0030-drops-210399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.46 eng https://creativecommons.org/licenses/by/4.0/legalcode