Testing Distributions of Huge Objects
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). Accord...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
TheoretiCS Foundation e.V.
2023-12-01
|
| Series: | TheoretiCS |
| Subjects: | |
| Online Access: | https://theoretics.episciences.org/10553/pdf |
| _version_ | 1797333144767037440 |
|---|---|
| author | Oded Goldreich Dana Ron |
| author_facet | Oded Goldreich Dana Ron |
| author_sort | Oded Goldreich |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-08T07:59:32Z |
| format | Article |
| id | doaj.art-5247fec72fe74c99bc2949a93e8c8383 |
| institution | Directory Open Access Journal |
| issn | 2751-4838 |
| language | English |
| last_indexed | 2024-03-08T07:59:32Z |
| publishDate | 2023-12-01 |
| publisher | TheoretiCS Foundation e.V. |
| record_format | Article |
| series | TheoretiCS |
| spelling | doaj.art-5247fec72fe74c99bc2949a93e8c83832024-02-02T12:32:47ZengTheoretiCS Foundation e.V.TheoretiCS2751-48382023-12-01Volume 210.46298/theoretics.23.1210553Testing Distributions of Huge ObjectsOded GoldreichDana RonWe 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.https://theoretics.episciences.org/10553/pdfcomputer science - data structures and algorithms |
| spellingShingle | Oded Goldreich Dana Ron Testing Distributions of Huge Objects TheoretiCS computer science - data structures and algorithms |
| title | Testing Distributions of Huge Objects |
| title_full | Testing Distributions of Huge Objects |
| title_fullStr | Testing Distributions of Huge Objects |
| title_full_unstemmed | Testing Distributions of Huge Objects |
| title_short | Testing Distributions of Huge Objects |
| title_sort | testing distributions of huge objects |
| topic | computer science - data structures and algorithms |
| url | https://theoretics.episciences.org/10553/pdf |
| work_keys_str_mv | AT odedgoldreich testingdistributionsofhugeobjects AT danaron testingdistributionsofhugeobjects |