Fiche du document
2 janvier 2024
- handle: 10670/1.oezdkh
- doi: 10.46298/theoretics.23.12
info:eu-repo/semantics/openAccess , info:eu-repo/semantics/openAccess
Sujets proches
Mechanical properties testingCiter ce document
Oded Goldreich et al., « Testing Distributions of Huge Objects », Episciences.org, ID : 10.46298/theoretics.23.12
Métriques
Partage / Export
Résumé
We initiate a study of a new model of property testing that is a hybrid oftesting properties of distributions and testing properties of strings.Specifically, the new model refers to testing properties of distributions, butthese are distributions over huge objects (i.e., very long strings).Accordingly, the model accounts for the total number of local probes into theseobjects (resp., queries to the strings) as well as for the distance betweenobjects (resp., strings), and the distance between distributions is defined asthe earth mover's distance with respect to the relative Hamming distancebetween strings. We study the query complexity of testing in this new model, focusing on threedirections. First, we try to relate the query complexity of testing propertiesin the new model to the sample complexity of testing these properties in thestandard distribution testing model. Second, we consider the complexity oftesting properties that arise naturally in the new model (e.g., distributionsthat capture random variations of fixed strings). Third, we consider thecomplexity of testing properties that were extensively studied in the standarddistribution testing model: Two such cases are uniform distributions and pairsof identical distributions.