Testing read-once formula satisfaction

Article English OPEN
Fischer, E.; Yonatan, G.; Oded, Lachish;
(2016)
  • Publisher: ACM
  • 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 Boolea... View more
  • 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.

  • Related Organizations (1)
  • Metrics
Share - Bookmark