Search Results

Documents authored by Adar, Tomer

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.32
Tight Simulation of a Distribution Using Conditional Samples

Authors: Tomer Adar

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
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.
Cite as

Tomer Adar. Tight Simulation of a Distribution Using Conditional Samples. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adar:LIPIcs.APPROX/RANDOM.2026.32,
  author =	{Adar, Tomer},
  title =	{{Tight Simulation of a Distribution Using Conditional Samples}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.32},
  URN =		{urn:nbn:de:0030-drops-277496},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.32},
  annote =	{Keywords: Distribution learning, Distribution simulation, Probability estimation}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.33
When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries

Authors: Tomer Adar, Yahel Hotam, and Amit Levi

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
We study the problem of estimating the number of edges in an unknown graph. We consider a hybrid model in which an algorithm may issue independent set, degree, and neighbor queries. We show that this model admits strictly more efficient edge estimation than either access type alone. Specifically, we give a randomized algorithm that outputs a (1±ε)-approximation of the number of edges using O(min(√m, √{n/√m})⋅(log n)/ε^{5/2}) queries, and prove a nearly matching lower bound. In contrast, prior work shows that in the local query model (Goldreich and Ron, Random Structures & Algorithms 2008) and in the independent set query model (Beame et al. ITCS 2018, Chen et al. SODA 2020), edge estimation requires Θ̃(n/√m) queries in the same parameter regimes. Our results therefore yield a quadratic improvement in the hybrid model, and no asymptotically better improvement is possible.
Cite as

Tomer Adar, Yahel Hotam, and Amit Levi. When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2026.33,
  author =	{Adar, Tomer and Hotam, Yahel and Levi, Amit},
  title =	{{When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.33},
  URN =		{urn:nbn:de:0030-drops-277509},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.33},
  annote =	{Keywords: Edge count estimation, Degree oracle, Neighbor oracle, Independent-set oracle}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.45
Refining the Adaptivity Notion in the Huge Object Model

Authors: Tomer Adar and Eldar Fischer

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
The Huge Object model for distribution testing, first defined by Goldreich and Ron in 2022, combines the features of classical string testing and distribution testing. In this model we are given access to independent samples from an unknown distribution P over the set of strings {0,1}ⁿ, but are only allowed to query a few bits from the samples. The distinction between adaptive and non-adaptive algorithms, which occurs naturally in the realm of string testing (while being irrelevant for classical distribution testing), plays a substantial role also in the Huge Object model. In this work we show that the full picture in the Huge Object model is much richer than just that of the adaptive vs. non-adaptive dichotomy. We define and investigate several models of adaptivity that lie between the fully-adaptive and the completely non-adaptive extremes. These models are naturally grounded by observing the querying process from each sample independently, and considering the "algorithmic flow" between them. For example, if we allow no information at all to cross over between samples (up to the final decision), then we obtain the locally bounded adaptive model, arguably the "least adaptive" one apart from being completely non-adaptive. A slightly stronger model allows only a "one-way" information flow. Even stronger (but still far from being fully adaptive) models follow by taking inspiration from the setting of streaming algorithms. To show that we indeed have a hierarchy, we prove a chain of exponential separations encompassing most of the models that we define.
Cite as

Tomer Adar and Eldar Fischer. Refining the Adaptivity Notion in the Huge Object Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2024.45,
  author =	{Adar, Tomer and Fischer, Eldar},
  title =	{{Refining the Adaptivity Notion in the Huge Object Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{45:1--45:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.45},
  URN =		{urn:nbn:de:0030-drops-210383},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.45},
  annote =	{Keywords: Huge-Object model, Property Testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.46
Support Testing in the Huge Object Model

Authors: Tomer Adar, Eldar Fischer, and Amit Levi

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
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.
Cite as

Tomer Adar, Eldar Fischer, and Amit Levi. Support Testing in the Huge Object Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2024.46,
  author =	{Adar, Tomer and Fischer, Eldar and Levi, Amit},
  title =	{{Support Testing in the Huge Object Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.46},
  URN =		{urn:nbn:de:0030-drops-210399},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.46},
  annote =	{Keywords: Huge-Object model, Property Testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.48
Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries

Authors: Tomer Adar, Eldar Fischer, and Amit Levi

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for n-dimensional distributions that is quasi-linear in n, improving the previously known Õ(n²/ε²) query complexity bound to Õ(n/ε²). We extend this result to general finite alphabets with logarithmic cost in the alphabet size. By exploiting the specific structure of the queries that we use (which are more restrictive than general subcube queries), we obtain a cubic improvement over the best known test for distributions over {1,…,N} under the interval querying model of Canonne, Ron and Servedio (2015), attaining a query complexity of Õ((log N)/ε²), which for fixed ε almost matches the known lower bound of Ω((log N)/log log N). We also derive a product test for n-dimensional distributions with Õ(n/ε²) queries, and provide an Ω(√n/ε²) lower bound for this property.
Cite as

Tomer Adar, Eldar Fischer, and Amit Levi. Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 48:1-48:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{adar_et_al:LIPIcs.APPROX/RANDOM.2024.48,
  author =	{Adar, Tomer and Fischer, Eldar and Levi, Amit},
  title =	{{Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{48:1--48:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.48},
  URN =		{urn:nbn:de:0030-drops-210418},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.48},
  annote =	{Keywords: Distribution testing, conditional sampling, sub-cube sampling}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact