{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:29Z","timestamp":1725563069392},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_35","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"462-475","source":"Crossref","is-referenced-by-count":3,"title":["Monotonicity Testing and Shortest-Path Routing on the Cube"],"prefix":"10.1007","author":[{"given":"Jop","family":"Bri\u00ebt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Garc\u00eda-Soriano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Al-Bashabsheh, A., Yonga\u00e7oglu, A.: On the k-pairs problem. CoRR, abs\/0805.0050 (2008)","DOI":"10.1109\/ISIT.2008.4595304"},{"issue":"11","key":"35_CR2","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1016\/j.ic.2006.06.001","volume":"204","author":"N. Ailon","year":"2006","unstructured":"Ailon, N., Chazelle, B.: Information theory in property testing and monotonicity testing in higher dimension. Inf. Comput.\u00a0204(11), 1704\u20131717 (2006)","journal-title":"Inf. Comput."},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"Adler, M., Harvey, N.J.A., Jain, K., Kleinberg, R.D., Lehman, A.R.: On the capacity of information networks. In: SODA, pp. 241\u2013250 (2006)","DOI":"10.1145\/1109557.1109585"},{"key":"35_CR4","volume-title":"Mathematical theory of connecting networks and telephone traffic","author":"V.E. Benes","year":"1965","unstructured":"Benes, V.E.: Mathematical theory of connecting networks and telephone traffic. Academic Press, New York (1965)"},{"key":"35_CR5","first-page":"932","volume-title":"SODA 2009: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms","author":"A. Bhattacharyya","year":"2009","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners. In: SODA 2009: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, pp. 932\u2013941. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners of the hypercube and the hypergrid. Electronic Colloquium on Computational Complexity (ECCC)\u00a009(046) (2009)","DOI":"10.1137\/1.9781611973068.101"},{"key":"35_CR7","unstructured":"Bhattacharyya, A.: A note on the distance to monotonicity of boolean functions. Electronic Colloquium on Computational Complexity (ECCC)\u00a015(012) (2008)"},{"key":"35_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-540-48413-4_10","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 97\u2013108. Springer, Heidelberg (1999)"},{"issue":"3","key":"35_CR9","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Erg\u00fcn","year":"2000","unstructured":"Erg\u00fcn, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci.\u00a060(3), 717\u2013751 (2000)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"35_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ic.2003.09.003","volume":"189","author":"E. Fischer","year":"2004","unstructured":"Fischer, E.: On the strength of comparisons in property testing. Inf. Comput.\u00a0189(1), 107\u2013116 (2004)","journal-title":"Inf. Comput."},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"3","key":"35_CR12","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"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D.: Testing monotonicity. In: FOCS, pp. 426\u2013435 (1998)","DOI":"10.1109\/SFCS.1998.743493"},{"issue":"1","key":"35_CR14","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1002\/rsa.20211","volume":"33","author":"S. Halevy","year":"2008","unstructured":"Halevy, S., Kushilevitz, E.: Testing monotonicity over graph products. Random Struct. Algorithms\u00a033(1), 44\u201367 (2008)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"35_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1006\/jcta.2000.3148","volume":"94","author":"E. Lehman","year":"2001","unstructured":"Lehman, E., Ron, D.: On disjoint chains of subsets. J. Comb. Theory, Ser. A\u00a094(2), 399\u2013404 (2001)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"2","key":"35_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(90)90106-8","volume":"35","author":"A. Lubiw","year":"1990","unstructured":"Lubiw, A.: Counterexample to a conjecture of szymanski on hypercube routing. Inf. Process. Lett.\u00a035(2), 57\u201361 (1990)","journal-title":"Inf. Process. Lett."},{"key":"35_CR17","volume-title":"Monotonicity testing. Master\u2019s thesis, Department of Electrical Engineering and Computer Science","author":"S. Raskhodnikova","year":"1999","unstructured":"Raskhodnikova, S.: Monotonicity testing. Master\u2019s thesis, Department of Electrical Engineering and Computer Science. MIT, Cambridge, MA (1999)"},{"key":"35_CR18","unstructured":"Rasala-Lehman, A.: Network coding. PhD thesis, Department of Electrical Engineering and Computer Science. MIT, Cambridge, MA (2005)"},{"key":"35_CR19","unstructured":"Szymanski, T.H.: On the permutation capability of a circuit-switched hypercube. In: ICPP (1), pp. 103\u2013110 (1989)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:28Z","timestamp":1606187128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}