{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:45Z","timestamp":1759638105817,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169878"},{"type":"electronic","value":"9783642169885"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16988-5_7","type":"book-chapter","created":{"date-parts":[[2010,10,23]],"date-time":"2010-10-23T03:14:03Z","timestamp":1287803643000},"page":"74-88","source":"Crossref","is-referenced-by-count":3,"title":["k \u2009+\u2009 Decision Trees"],"prefix":"10.1007","author":[{"given":"James","family":"Aspnes","sequence":"first","affiliation":[]},{"given":"Eric","family":"Blais","sequence":"additional","affiliation":[]},{"given":"Murat","family":"Demirbas","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"O\u2019Donnell","sequence":"additional","affiliation":[]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[]},{"given":"Steve","family":"Uurtamo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Aigner, M.: Combinatorial Search. Wiley-Teubner Series in Computer Science (1988)"},{"issue":"5","key":"7_CR2","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.comnet.2004.06.007","volume":"46","author":"A. Arora","year":"2004","unstructured":"Arora, A., Dutta, P., Bapat, S., Kulathumani, V., Zhang, H., Naik, V., Mittal, V., Cao, H., Demirbas, M., Gouda, M., Choi, Y.R., Herman, T., Kulkarni, S.S., Arumugam, U., Nesterenko, M., Vora, A., Miyashita, M.: A line in the sand: A wireless sensor network for target detection, classification, and tracking. Computer Networks (Elsevier)\u00a046(5), 605\u2013634 (2004)","journal-title":"Computer Networks (Elsevier)"},{"issue":"3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1006\/jcss.1995.1085","volume":"51","author":"Y. Ben-Asher","year":"1995","unstructured":"Ben-Asher, Y., Newman, I.: Decision trees with boolean threshold queries. J. Comput. Syst. Sci.\u00a051(3), 495\u2013502 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: STOC 1983, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(96)00077-4","volume":"59","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H.: A subexponential exact learning algorithm for DNF using equivalence queries. Information Processing Letters\u201d\u00a059(3), 37\u201339 (1996)","journal-title":"Information Processing Letters\u201d"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: A survey. Theoretical Computer Science\u00a0288(1), 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00446-008-0056-2","volume":"21","author":"G. Chockler","year":"2008","unstructured":"Chockler, G., Demirbas, M., Gilbert, S., Lynch, N.A., Newport, C.C., Nolte, T.: Consensus and collision detectors in radio networks. Distributed Computing\u00a021(1), 55\u201384 (2008)","journal-title":"Distributed Computing"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Demirbas, M., Soysal, O., Hussain, M.: Singlehop collaborative feedback primitives for wireless sensor networks. In: INFOCOM, pp. 2047\u20132055 (2008)","DOI":"10.1109\/INFOCOM.2008.270"},{"issue":"2","key":"7_CR9","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D. Dobkin","year":"1976","unstructured":"Dobkin, D., Lipton, R.J.: Multidimensional searching problems. SIAM Journal on Computing\u00a05(2), 181\u2013186 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR10","volume-title":"Combinatorial Group Testing and its Applications","author":"D.Z. Du","year":"2000","unstructured":"Du, D.Z., Hwang, F.K.: Combinatorial Group Testing and its Applications. World Scientific, Singapore (2000)"},{"key":"7_CR11","unstructured":"Dutta, P., Musaloiu-e, R., Stoica, I., Terzis, A.: Wireless ack collisions not considered harmful. In: HotNets-VII: The Seventh Workshop on Hot Topics in Networks (2008)"},{"issue":"3","key":"7_CR12","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D.: Learning decision trees from random examples. Information and Computation\u00a082(3), 231\u2013246 (1989)","journal-title":"Information and Computation"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1145\/1148109.1148132","volume-title":"SPAA 2006: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures","author":"M.T. Goodrich","year":"2006","unstructured":"Goodrich, M.T., Hirschberg, D.S.: Efficient parallel algorithms for dead sensor diagnosis and multiple access channels. In: SPAA 2006: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 118\u2013127. ACM, New York (2006)"},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0167-7152(94)00090-U","volume":"23","author":"K. Hamza","year":"1995","unstructured":"Hamza, K.: The smallest uniform upper bound on the distance between the mean and the median of the binomial and Poisson distributions. Statistics and Probability Letters\u00a023(1), 21\u201325 (1995)","journal-title":"Statistics and Probability Letters"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-45655-4_31","volume-title":"Computing and Combinatorics","author":"T. Jurdzinski","year":"2002","unstructured":"Jurdzinski, T., Kutylowski, M., Zatopianski, J.: Energy-efficient size approximation of radio networks with no collision detection. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 279\u2013289. Springer, Heidelberg (2002)"},{"issue":"6","key":"7_CR16","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the fourier spectrum. SIAM Journal on Computing\u00a022(6), 1331\u20131348 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR17","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)"},{"issue":"4","key":"7_CR18","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1145\/4221.4259","volume":"32","author":"S. Moran","year":"1985","unstructured":"Moran, S., Snir, M., Manber, U.: Applications of ramsey\u2019s theorem to decision tree complexity. J. ACM\u00a032(4), 938\u2013949 (1985)","journal-title":"J. ACM"},{"issue":"6","key":"7_CR19","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N. Nisan","year":"1991","unstructured":"Nisan, N.: CREW PRAMs and decision trees. SIAM Journal on Computing\u00a020(6), 999\u20131007 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: STOC 1992, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"issue":"4","key":"7_CR21","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1008299.1008302","volume":"5","author":"A.L. Rosenberg","year":"1973","unstructured":"Rosenberg, A.L.: On the time required to recognize properties of graphs: a problem. SIGACT News\u00a05(4), 15\u201316 (1973)","journal-title":"SIGACT News"},{"issue":"3","key":"7_CR22","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/0217031","volume":"17","author":"A.C.C. Yao","year":"1988","unstructured":"Yao, A.C.C.: Monotone bipartite graph properties are evasive. SIAM Journal on Computing\u00a017(3), 517\u2013520 (1988)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Sensor Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16988-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T22:04:53Z","timestamp":1578521093000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16988-5_7"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169878","9783642169885"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16988-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}