Showing 2024Show all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…