{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:24:54Z","timestamp":1725582294948},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_32","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T06:35:17Z","timestamp":1303886117000},"page":"320-331","source":"Crossref","is-referenced-by-count":10,"title":["Lower Bounds for Testing Computability by Small Width OBDDs"],"prefix":"10.1007","author":[{"given":"Joshua","family":"Brody","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Matulef","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenggang","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"32_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"175","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science\u00a0175(2), 139\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-540-27821-4_24","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Z. Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: The sketching complexity of pattern matching. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 261\u2013272. Springer, Heidelberg (2004)"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/3-540-62685-9_13","volume-title":"Computational Learning Theory","author":"F. Bergadano","year":"1997","unstructured":"Bergadano, F., Bshouty, N.H., Tamon, C., Varricchio, S.: On learning branching programs and small depth circuits. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol.\u00a01208, pp. 150\u2013161. Springer, Heidelberg (1997)"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Blais, E.: Improved bounds for testing juntas. In: Proc. 12th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 317\u2013330 (2008)","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proc. 41st Annual ACM Symposium on the Theory of Computing, pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity (2011), \n                      \n                        http:\/\/web.mit.edu\/matulef\/www\/papers\/PTviaCC.pdf","DOI":"10.1109\/CCC.2011.31"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comput. Syst. Sci.\u00a047, 549\u2013595 (1993); Earlier version in STOC 1990","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0020-0190(97)00204-4","volume":"65","author":"N.H. Bshouty","year":"1998","unstructured":"Bshouty, N.H., Tamon, C., Wilson, D.K.: On learning width two branching programs. Inf. Process. Lett.\u00a065, 217\u2013222 (1998)","journal-title":"Inf. Process. Lett."},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., Wan, A.: Testing for concise representations. In: Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"Do Ba, K., Indyk, P., Price, E., Woodruff, D.P.: Lower bounds for sparse recovery. In: Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (2010)","DOI":"10.1137\/1.9781611973075.95"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubenfeld, R.: On learning boundedwidth branching programs. In: Proc. 8th International Conference on Learning Theory, pp. 361\u2013368 (1995)","DOI":"10.1145\/225298.225342"},{"key":"32_CR12","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. J. Comput. Syst. Sci.\u00a068, 753\u2013787 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proc. 34th Annual ACM Symposium on the Theory of Computing, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"key":"32_CR14","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Learning Theory","author":"R. Gavald\u2018a","year":"1995","unstructured":"Gavald\u2018a, R., Guijarro, D.: Learning ordered binary decision diagrams. In: Jantke, K.P., Shinohara, T., Zeugmann, T. (eds.) ALT 1995. LNCS, vol.\u00a0997, Springer, Heidelberg (1995)"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On testing computability by small width OBDDs. In: Proc. 14th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 574\u2013587 (2010)","DOI":"10.1007\/978-3-642-15369-3_43"},{"issue":"3","key":"32_CR16","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica\u00a020(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"4","key":"32_CR17","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Wigderson, A.: The randomized communication complexity of set disjointness. Theory of Computing, 211\u2013219 (2007)","DOI":"10.4086\/toc.2007.v003a011"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: On the exact space complexity of sketching and streaming small norms. In: Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (2010)","DOI":"10.1137\/1.9781611973075.93"},{"key":"32_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"Magniez, F., Mathieu, C., Nayak, A.: Recognizing well-parenthesized expressions in the streaming model. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010 (2010)","DOI":"10.1145\/1806689.1806727"},{"issue":"1","key":"32_CR22","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIAM J. Disc. Math.\u00a016(1), 20\u201346 (2002)","journal-title":"SIAM J. Disc. Math."},{"key":"32_CR23","doi-asserted-by":"crossref","unstructured":"Raghavan, V., Wilkins, D.: Learning branching programs with queries. In: Proc. 6th Annual Workshop on Computational Learning Theory (1993)","DOI":"10.1145\/168304.168308"},{"issue":"2","key":"32_CR24","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2009","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science\u00a05(2), 73\u2013205 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"32_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/978-3-642-03685-9_51","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Ron","year":"2009","unstructured":"Ron, D., Tsur, G.: Testing computability by width two oBDDs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 686\u2013699. Springer, Heidelberg (2009)"},{"key":"32_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-642-13073-1_13","volume-title":"Algorithms and Complexity","author":"D. Ron","year":"2010","unstructured":"Ron, D., Tsur, G.: Testing computability by width-2 oBDDs where the variable order is unknown. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol.\u00a06078, pp. 131\u2013142. Springer, Heidelberg (2010)"},{"key":"32_CR27","unstructured":"Ron, D., Tsur, G.: Personal communication (2011)"},{"key":"32_CR28","doi-asserted-by":"crossref","unstructured":"Ron, D., Tsur, G.: Testing computability by width-two obdds (Journal version) (2011) (manuscript)","DOI":"10.1016\/j.tcs.2011.11.007"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T05:16:01Z","timestamp":1558588561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}