4 papers · 1 filter
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…
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…
A basic lower bound for property testing
Eldar Fischer
An -test for any non-trivial property (one for which there are both satisfying inputs and inputs of large distance from the property) should use a number of queries that is at…