EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Testing Distributions of Huge Objects

Oded Goldreich, Dana Ron

TheoretiCS · 2023

DOI: 10.46298/theoretics.23.12 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von Oded Goldreich und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings. Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings). Accordingly, the model accounts for the total number of local probes into these objects (resp., queries to the strings) as well as for the distance between objects (resp., strings), and the distance between distributions is defined as the earth mover's distance with respect to the relative Hamming distance between strings. We study the query complexity of testing in this new model, focusing on three directions. First, we try to relate the query complexity of testing properties in the new model to the sample complexity of testing these properties in the standard distribution testing model. Second, we consider the complexity of testing properties that arise naturally in the new model (e.g., distributions that capture random variations of fixed strings). Third, we consider the complexity of testing properties that were extensively studied in the standard distribution testing model: Two such cases are uniform distributions and pairs of identical distributions.

Zitieren

APA

Goldreich, O., & Ron, D. (2023). Testing Distributions of Huge Objects. TheoretiCS. https://doi.org/10.46298/theoretics.23.12

Vancouver

Goldreich O, Ron D. Testing Distributions of Huge Objects. TheoretiCS. 2023. doi:10.46298/theoretics.23.12

BibTeX
@article{Goldreich2023,
  author = {Goldreich, Oded and Ron, Dana},
  title = {Testing Distributions of Huge Objects},
  journal = {TheoretiCS},
  year = {2023},
  doi = {10.46298/theoretics.23.12}
}
Kostenlos starten →