5 papers
Instance-optimal estimation of L2-norm
Tomer Adar
The -norm, or collision norm, is a core entity in the analysis of distributions and probabilistic algorithms. Batu and Canonne (FOCS 2017) presented an extensive analysis of a…
Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
Tomer Adar, Amit Levi
A central theme in sublinear graph algorithms is the relationship between counting and sampling: can the ability to approximately count a combinatorial structure be leveraged to sa…
When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
Tomer Adar, Yahel Hotam, Amit Levi
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…
Tight simulation of a distribution using conditional samples
Tomer Adar
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 t…
Optimal mass estimation in the conditional sampling model
Tomer Adar, Eldar Fischer, Amit Levi
The conditional sampling model, introduced by Cannone, Ron and Servedio (SODA 2014, SIAM J. Comput. 2015) and independently by Chakraborty, Fischer, Goldhirsh and Matsliah (ITCS 20…