Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on {0,1} n , where n is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by the total number of queries that were made to them. Index-invariant properties under this model were defined in [Chakraborty et al., COLT 23], as a compromise between enduring the full intricacies of string testing when considering unconstrained properties, and giving up completely on the string structure when considering label-invariant properties. Index-invariant properties are those that are invariant through a consistent reordering of the bits of the involved strings. Here we provide an adaptation of Szemerédi’s regularity method for this setting, and in particular show that if an index-invariant property admits an є-test with a number of queries depending only on the proximity parameter є, then it also admits a distance estimation algorithm whose number of queries depends only on the approximation parameter.

Authors

• Sourav Chakraborty 0001
• Eldar Fischer
• Arijit Ghosh
• Amit Levi
• Gopinath Mishra
• Sayantan Sen

Keywords

No keywords are indexed for this paper.