Testing read-once formula satisfaction

Article English OPEN
Fischer, E. ; Yonatan, G. ; Oded, Lachish (2016)
  • Publisher: ACM
  • Related identifiers: doi: 10.1145/2897184
  • Subject: csis
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES

We study the query complexity of testing for properties defined by read once formulas, as instances of {\em massively parametrized properties}, and prove several testability and non-testability results. First we prove the testability of any property accepted by a Boolean read-once formula involving any bounded arity gates, with a number of queries exponential in $\epsilon$, doubly exponential in the arity, and independent of all other parameters. When the gates are limited to being monotone, we prove that there is an {\em estimation} algorithm, that outputs an approximation of the distance of the input from satisfying the property. For formulas only involving And/Or gates, we provide a more efficient test whose query complexity is only quasipolynomial in $\epsilon$. On the other hand, we show that such testability results do not hold in general for formulas over non-Boolean alphabets; specifically we construct a property defined by a read-once arity $2$ (non-Boolean) formula over an alphabet of size $4$, such that any $1/4$-test for it requires a number of queries depending on the formula size. We also present such a formula over an alphabet of size $5$ that additionally satisfies a strong monotonicity condition.
  • References (17)
    17 references, page 1 of 2

    Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. 2000. Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. 30, 6 (2000), 1842-1862.

    Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah. 2009. Sound 3-Query PCPPs Are Long. ACM Trans. Comput. Theory 1 (September 2009), 7:1-7:49. Issue 2.

    Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. 2005. Some 3CNF Properties Are Hard to Test. SIAM J. Comput. 35, 1 (2005), 1-21.

    Manuel Blum, Michael Luby, and Ronitt Rubinfeld. 1993. Self-Testing/Correcting with Applications to Numerical Problems. J. Comput. Syst. Sci. 47, 3 (1993), 549-595.

    Sourav Chakraborty, Eldar Fischer, Oded Lachish, Arie Matsliah, and Ilan Newman. 2007. Testing st - Connectivity. In APPROX-RANDOM. 380-394.

    Eldar Fischer. 2004. The art of uninformed decisions: A primer to property testing. Current Trends in Theoretical Computer Science: The Challenge of the New Century I (2004), 229-264.

    Eldar Fischer, Ilan Newman, and Jiri Sgall. 2004. Functions that have read-twice constant width branching programs are not necessarily testable. Random Struct. Algorithms 24, 2 (2004), 175-193.

    Eldar Fischer and Orly Yahalom. 2011. Testing Convexity Properties of Tree Colorings. Algorithmica 60, 4 (2011), 766-805.

    Oded Goldreich. 2010. A Brief Introduction to Property Testing. In Property Testing, Oded Goldreich (Ed.). Springer-Verlag, 1-5.

    Oded Goldreich, Shaffi Goldwasser, and Dana Ron. 1998. Property testing and its connection to learning and approximation. J. ACM 45 (July 1998), 653-750. Issue 4.

  • Similar Research Results (1)
  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    29
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Birkbeck Institutional Research Online - IRUS-UK 0 29
Share - Bookmark