Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Fischer, E.; Yonatan, G.; Oded, Lachish (2016)
Publisher: ACM
Languages: English
Types: Article
Subjects: csis

Classified by OpenAIRE into

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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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.
    • Shirley Halevy, Oded Lachish, Ilan Newman, and Dekel Tsur. 2005. Testing Orientation Properties. Electronic Colloquium on Computational Complexity (ECCC) 153 (2005).
    • Shirley Halevy, Oded Lachish, Ilan Newman, and Dekel Tsur. 2007. Testing Properties of Constraint-Graphs. In IEEE Conference on Computational Complexity. 264-277.
    • Ilan Newman. 2002. Testing Membership in Languages that Have Small Width Branching Programs. SIAM J. Comput. 31, 5 (2002), 1557-1570.
    • Ilan Newman. 2010. Property Testing of Massively Parametrized Problems - A Survey. In Property Testing, Oded Goldreich (Ed.). Springer-Verlag, 142-157.
    • Dana Ron. 2008. Property Testing: A Learning Theory Perspective. Found. Trends Mach. Learn. 1 (March 2008), 307-402. Issue 3.
    • Dana Ron. 2010. Algorithmic and Analysis Techniques in Property Testing.
    • Ronitt Rubinfeld and Madhu Sudan. 1996. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25, 2 (1996), 252-271.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Funded by projects


Cite this article