Oded Goldreich ; Dana Ron - Testing Distributions of Huge Objects

theoretics:10553 - TheoretiCS, December 30, 2023, Volume 2 - https://doi.org/10.46298/theoretics.23.12
Testing Distributions of Huge ObjectsArticle

Authors: Oded Goldreich ; Dana Ron

    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.


    Volume: Volume 2
    Published on: December 30, 2023
    Accepted on: November 12, 2023
    Submitted on: December 28, 2022
    Keywords: Computer Science - Data Structures and Algorithms
    Funding:
      Source : OpenAIRE Graph
    • Foundations of Verifiable Computing; Funder: European Commission; Code: 819702

    Consultation statistics

    This page has been seen 241 times.
    This article's PDF has been downloaded 106 times.