Testing computability by width-two OBDDs. (English) Zbl 1234.68462
Summary: Property testing is concerned with deciding whether an object (e.g. a graph or a function) has a certain property or is “far” (for a prespecified distance measure) from every object with that property. In this work, we consider the property of being computable by a read-once width-2 ordered binary decision diagram (OBDD), also known as a branching program, in two settings. In the first setting, the order of the variables is fixed and given to the algorithm, while in the second setting it is not fixed. That is, while in the first setting we should accept a function \(f\) if it is computable by a width-2 OBDD with a given order of the variables, in the second setting we should accept a function \(f\) if there exists an order of the variables according to which a width-2 OBDD can compute \(f\).
Width-2 OBDDs generalize two classes of functions that have been studied in the context of property testing: linear functions (over \(GF(2)\)) and monomials. In both these cases membership can be tested by performing a number of queries that is independent of the number of variables, \(n\) (and is linear in \(1/\epsilon\), where \(\epsilon\) is the distance parameter). In contrast, we show that testing computability by width- OBDDs when the order of variables is fixed and known requires a number of queries that grows logarithmically with \(n\) (for a constant \(\epsilon\)), and we provide an algorithm that performs \(\tilde O(\log n/ \epsilon)\) queries. For the case where the order is not fixed, we show that there is no testing algorithm that performs a number of queries that is sublinear in \(n\).
Width-2 OBDDs generalize two classes of functions that have been studied in the context of property testing: linear functions (over \(GF(2)\)) and monomials. In both these cases membership can be tested by performing a number of queries that is independent of the number of variables, \(n\) (and is linear in \(1/\epsilon\), where \(\epsilon\) is the distance parameter). In contrast, we show that testing computability by width- OBDDs when the order of variables is fixed and known requires a number of queries that grows logarithmically with \(n\) (for a constant \(\epsilon\)), and we provide an algorithm that performs \(\tilde O(\log n/ \epsilon)\) queries. For the case where the order is not fixed, we show that there is no testing algorithm that performs a number of queries that is sublinear in \(n\).
References:
| [1] | Alon, N.; Krivelevich, M.; Kaufman, T.; Litsyn, S.; Ron, D., Testing Reed-Muller codes, IEEE Transactions on Information Theory, 51, 11, 4032-4038 (2005) · Zbl 1247.94057 |
| [2] | F. Bergadano, N. Bshouty, C. Tamon, S. Varricchio, On learning branching programs and small depth circuits, in: Proceedings of the Tenth Annual ACM Conference on Computational Learning Theorey, COLT, 1997, pp. 150-161.; F. Bergadano, N. Bshouty, C. Tamon, S. Varricchio, On learning branching programs and small depth circuits, in: Proceedings of the Tenth Annual ACM Conference on Computational Learning Theorey, COLT, 1997, pp. 150-161. |
| [3] | E. Blais, J. Brody, K. Matulef, Property testing lower bounds via communication complexity, in: The 26th Conference on Computational Complexity, CCC, 2011, pp. 210-220.; E. Blais, J. Brody, K. Matulef, Property testing lower bounds via communication complexity, in: The 26th Conference on Computational Complexity, CCC, 2011, pp. 210-220. · Zbl 1253.68142 |
| [4] | Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, Journal of the ACM, 47, 549-595 (1993) · Zbl 0795.68131 |
| [5] | J. Brody, K. Matulef, C. Wu, Lower bounds for testing computability by small width OBDDs, Manuscript, 2011.; J. Brody, K. Matulef, C. Wu, Lower bounds for testing computability by small width OBDDs, Manuscript, 2011. · Zbl 1331.68088 |
| [6] | Bshouty, N.; Tamon, C.; Wilson, D., On learning width two branching programs, Information Processing Letters, 65, 217-222 (1998) · Zbl 1339.68129 |
| [7] | I. Diakonikolas, H.K. Lee, K. Matulef, K. Onak, R. Rubinfeld, R.A. Servedio, A. Wan, Testing for concise representations, in: Proceedings of the Forty-Eighth Annual Symposium on Foundations of Computer Science, FOCS, 2007, pp. 549-557.; I. Diakonikolas, H.K. Lee, K. Matulef, K. Onak, R. Rubinfeld, R.A. Servedio, A. Wan, Testing for concise representations, in: Proceedings of the Forty-Eighth Annual Symposium on Foundations of Computer Science, FOCS, 2007, pp. 549-557. |
| [8] | F. Ergün, R.S. Kumar, R. Rubinfeld, On learning bounded-width branching programs, in: Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory, COLT, 1995, pp. 361-368.; F. Ergün, R.S. Kumar, R. Rubinfeld, On learning bounded-width branching programs, in: Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory, COLT, 1995, pp. 361-368. |
| [9] | Fischer, E., The art of uninformed decisions: a primer to property testing, Bulletin of the European Association for Theoretical Computer Science, 75, 97-126 (2001) · Zbl 1024.68045 |
| [10] | Fischer, E.; Kindler, G.; Ron, D.; Safra, S.; Samorodnitsky, S., Testing juntas, Journal of Computer and System Sciences, 68, 4, 753-787 (2004) · Zbl 1076.68112 |
| [11] | R. Gavalda, D. Guijarro, Learning ordered binary decision diagrams, in: Proceedings of the Sixth Interntional Conference on Algorithmic Learning Theory, ALT, 1995, pp. 228-238.; R. Gavalda, D. Guijarro, Learning ordered binary decision diagrams, in: Proceedings of the Sixth Interntional Conference on Algorithmic Learning Theory, ALT, 1995, pp. 228-238. · Zbl 1527.68105 |
| [12] | O. Goldreich, Combinatorial property testing — a survey, in: Randomization Methods in Algorithm Design, 1998, pp. 45-60.; O. Goldreich, Combinatorial property testing — a survey, in: Randomization Methods in Algorithm Design, 1998, pp. 45-60. |
| [13] | O. Goldreich, On testing computability by small width OBDDs, in: Proceedings of the Fourteenth International Workshop on Randomization and Computation, RANDOM, 2010, pp. 574-587.; O. Goldreich, On testing computability by small width OBDDs, in: Proceedings of the Fourteenth International Workshop on Randomization and Computation, RANDOM, 2010, pp. 574-587. · Zbl 1305.68330 |
| [14] | Goldreich, O.; Goldwasser, S.; Ron, D., Property testing and its connection to learning and approximation, Journal of the ACM, 45, 4, 653-750 (1998) · Zbl 1065.68575 |
| [15] | C.S. Jutla, A.C. Patthak, A. Rudra, D. Zuckerman, Testing low-degree polynomials over prime fields, in: Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, FOCS, 2004.; C.S. Jutla, A.C. Patthak, A. Rudra, D. Zuckerman, Testing low-degree polynomials over prime fields, in: Proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science, FOCS, 2004. · Zbl 1216.94068 |
| [16] | Kearns, M.; Ron, D., Testing problems with sub-learning sample complexity, Journal of Computer and System Sciences, 61, 3, 428-456 (2000) · Zbl 0970.68074 |
| [17] | Kushilevitz, E.; Nisan, N., Communication Complexity (1997), Cambridge University Press · Zbl 0869.68048 |
| [18] | Nakamura, A., Query learning of bounded-width OBDDs, Theoretical Computer Science, 241, 83-114 (2000) · Zbl 0944.68157 |
| [19] | Nakamura, A., An efficient query learning algorithm for OBDDs, Information and Computation, 201, 178-198 (2005) · Zbl 1088.68153 |
| [20] | Newman, I., Testing membership in languages that have small width branching programs, SIAM Journal on Computing, 31, 5, 1557-1570 (2002) · Zbl 1051.68069 |
| [21] | Parnas, M.; Ron, D.; Samorodnitsky, A., Testing basic boolean formulae, SIAM Journal on Discrete Mathematics, 16, 1, 20-46 (2002) · Zbl 1041.68050 |
| [22] | V. RagHavan, D. Wilkins, Learning branching programs with queries, in: Proceedings of the Sixth Annual ACM Conference on Computational Learning Theorey, COLT, 1993, pp. 27-36.; V. RagHavan, D. Wilkins, Learning branching programs with queries, in: Proceedings of the Sixth Annual ACM Conference on Computational Learning Theorey, COLT, 1993, pp. 27-36. |
| [23] | Razborov, A. A., On the distributional complexity of disjointness, Theoretical Computer Science, 106, 2, 385-390 (1992) · Zbl 0787.68055 |
| [24] | Ron, D., Property testing: a learning theory perspective, Foundations and Trends in Machine Learning, 1, 3, 307-402 (2008) |
| [25] | Ron, D., Algorithmic and analysis techniques in property testing, Foundations and Trends in Theoretical Computer Science, 5, 2, 73-205 (2010) · Zbl 1184.68610 |
| [26] | D. Ron, G. Tsur, Testing computability by width two OBDDs, in: Proceedings of the Thirteenth International Workshop on Randomization and Computation, RANDOM, 2009, pp. 686-699.; D. Ron, G. Tsur, Testing computability by width two OBDDs, in: Proceedings of the Thirteenth International Workshop on Randomization and Computation, RANDOM, 2009, pp. 686-699. · Zbl 1255.68296 |
| [27] | D. Ron, G. Tsur, Testing computability by width-two obdds where the variable order is unknown, in: Proceedings of the Seventh International Conference on Algorithms and Complexity, CIAC, 2010.; D. Ron, G. Tsur, Testing computability by width-two obdds where the variable order is unknown, in: Proceedings of the Seventh International Conference on Algorithms and Complexity, CIAC, 2010. · Zbl 1284.68650 |
| [28] | Rubinfeld, R.; Sudan, M., Robust characterization of polynomials with applications to program testing, SIAM Journal on Computing, 25, 2, 252-271 (1996) · Zbl 0844.68062 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
