2026-09-10T09:44:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27749 2026-09-09T12:19:36Z ddc:004 open_access

Tight Simulation of a Distribution Using Conditional Samples Adar, Tomer Distribution learning Distribution simulation Probability estimation We present an algorithm for simulating a distribution using prefix conditional samples (Adar, Fischer and Levi, 2024), as well as "prefix-compatible" conditional models such as the interval model (Cannone, Ron and Servedio, 2015) and the subcube model (CRS15, Bhattacharyya and Chakraborty, 2018). The sample complexity is O(log² N/ε²) prefix conditional samples per query, which improves on the previously known Õ(log³ N/ε²) (Kumar, Meel and Pote, 2025). Moreover, our simulating distribution is O(ε²)-close to the input distribution with respect to the Kullback-Leibler divergence, which is stricter than the usual guarantee of being O(ε)-close with respect to the total-variation distance. We show that our algorithm is tight with respect to the highly-related task of estimation: every algorithm that is able to estimate the mass of individual elements within (1 ± ε)-multiplicative error must make Ω(log²N/ε²) prefix conditional samples per element. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomer Adar 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.32 urn:nbn:de:0030-drops-277496 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.32 eng https://creativecommons.org/licenses/by/4.0/legalcode