6 papers
Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
Tomer Adar, Eldar Fischer, Amit Levi
We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for -dimensional distribution…
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
Oded Lachish, Amit Levi, Ilan Newman +1
We consider graph property testing in -degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by s…
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…
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…
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +3
The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on , where is so large that even reading…