Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024★ 1 cited
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.DS2016
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément L. Canonne, Talya Eden +2
A function is a -junta if it depends on at most of its variables. We consider the problem of tolerant testing of -juntas, where the test…