Abstract
We take another step in the study of the testability of small-width OBDDs, initiated by Ron and Tsur (Random’09). That is, we consider algorithms that, given oracle access to a function f:{0,1}n →{0,1}, need to determine whether f can be implemented by some restricted class of OBDDs or is far from any such function.
Ron and Tsur showed that testing whether a function f:{0,1}n →{0,1} is implementable by a width-2 OBDD has query complexity Θ(logn). Thus, testing width-2 OBDD functions is significantly easier than learning such functions (which requires Ω(n) queries). We show that such exponential gaps do not hold for several related classes. Specifically:
-
1
Testing whether f:{0,1}n →{0,1} is implementable by a width-4 OBDD requires \(\Omega(\sqrt{n})\) queries.
-
1
Testing whether f:GF(3)n→GF(3) is a linear function with 0-1 coefficients requires \(\Omega(\sqrt{n})\) queries. Note that this class of functions is a subset of the class of all linear functions over GF(3), and that each such linear function can be implemented by a width-3 OBDD.
-
1
There exists a subclass \({\mathcal C}\) of the linear functions from GF(2)n to GF(2) such that testing membership in \({\mathcal C}\) has query complexity Θ(n). Note that each linear function over GF(2) can be implemented by a width-2 OBDD.
Recall that each of these classes has a proper learning algorithm of query complexity O(n).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple Constructions of Almost k-wise Independent Random Variables. Journal of Random Structures and Algorithms 3(3), 289–304 (1992)
Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. In: SICOMP, pp. 1842–1862 (2001)
Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M., Sudan, M.: Linearity testing in characteristic two. In: 36th FOCS, pp. 432–441 (1995)
Blais, E.: Testing juntas almost optimally. In: 41st STOC, pp. 151–158 (2009)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. JCSS 47(3), 549–595 (1993)
Diakonikolas, I., Lee, H.K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R.A., Wan, A.: Testing for concise representations. In: 48th FOCS, pp. 549–557 (2007)
Diakonikolas, I., Lee, H.K., Matulef, K., Servedio, R.A., Wan, A.: Efficient testing of sparse GF(2) polynomials. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 502–514. Springer, Heidelberg (2008)
Even, G.: Construction of Small Probabilistic Spaces for Deterministic Simulation. M.Sc. Thesis, Computer Science Dept., Technion – Israel Institute of Technology (August 1991) (in Hebrew, abstract in English)
Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, S.: Testing Juntas. JCSS 68(4), 753–787 (2004)
Goldreich, O.: On Testing Computability by Small Width OBDDs. ECCC, TR10-061 (2010)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 1996, 653–750 (1998)
Goldreich, O., Krivelevich, M., Newman, I., Rozenberg, E.: Hierarchy Theorems for Property Testing. ECCC, TR08-097 (2008)
Goldreich, O., Ron, D.: On Proximity Oblivious Testing. ECCC, TR08-041 (2008); Extended abstract in the proceedings of the 41st STOC (2009)
Lachish, O., Newman, I., Shapira, A.: Space Complexity vs. Query Complexity. Computational Complexity 17, 70–93 (2008)
Naor, J., Naor, M.: Small-bias Probability Spaces: Efficient Constructions and Applications. SICOMP 22, 838–856 (1993)
Newman, I.: Testing membership in languages that have small width branching programs. SIAM Journal on Computing 31(5), 1557–1570 (2002)
Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIDMA 16(1), 20–46 (2002)
Ron, D.: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning 1(3), 307–402 (2008)
Ron, D.: Algorithmic and Analysis Techniques in Property Testing. In: Foundations and Trends in TCS (to appear)
Ron, D., Tsur, G.: Testing Computability by Width Two OBDDs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) RANDOM 2009. LNCS, vol. 5687, pp. 686–699. Springer, Heidelberg (2009)
Ron, D., Tsur, G.: Testing Computability by Width Two OBDDs where the Variable Order is Unknown. In: 7th CIAC (to appear)
Rubinfeld, R.: On the Robustness of Functional Equations. SIAM Journal on Computing 28(6), 1972–1997 (1999)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldreich, O. (2010). On Testing Computability by Small Width OBDDs. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)