2026-08-07T09:32:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22654 2026-04-17T05:31:53Z ddc:004 open_access

Settling the Complexity of Testing Grainedness of Distributions, and Application to Uniformity Testing in the Huge Object Model Canonne, Clément L. Sen, Sayantan Yang, Joy Qiping Distribution testing Uniformity testing Huge Object Model Lower bounds In this work, we study the problem of testing m-grainedness of probability distributions over an n-element universe 𝒰, or, equivalently, of whether a probability distribution is induced by a multiset S ⊆ 𝒰 of size |S| = m. Recently, Goldreich and Ron (Computational Complexity, 2023) proved that Ω(n^c) samples are necessary for testing this property, for any c < 1 and m = Θ(n). They also conjectured that Ω(m/(log m)) samples are necessary for testing this property when m = Θ(n). In this work, we positively settle this conjecture. Using a known connection to the Distribution over Huge objects (DoHo) model introduced by Goldreich and Ron (TheoretiCS, 2023), we leverage our results to provide improved bounds for uniformity testing in the DoHo model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Clément L. Canonne and Sayantan Sen and Joy Qiping Yang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.26 urn:nbn:de:0030-drops-226543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode