Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributionsTransactions of the American Mathematical Society, 2019
- A short proof of Gowers’ lower bound for the regularity lemmaCombinatorica, 2014
- Large Networks and Graph Limits2012
- Testing properties of graphs and functionsIsrael Journal of Mathematics, 2010
- Concentration of Measure for the Analysis of Randomized Algorithms2009
- Limits of dense graph sequencesJournal of Combinatorial Theory, Series B, 2006
- Tolerant property testing and distance approximationJournal of Computer and System Sciences, 2006
- Tolerant Versus Intolerant Testing for Boolean Properties2005
- Quick Approximation to Matrices and ApplicationsCombinatorica, 1999
- On graphs with small subgraphs of large chromatic numberGraphs and Combinatorics, 1985