{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:01:54Z","timestamp":1775282514809,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00493-012-2765-1","type":"journal-article","created":{"date-parts":[[2012,2,10]],"date-time":"2012-02-10T03:19:34Z","timestamp":1328843974000},"page":"35-53","source":"Crossref","is-referenced-by-count":27,"title":["Monotonicity testing and shortest-path routing on the cube"],"prefix":"10.1007","volume":"32","author":[{"given":"Jop","family":"Bri\u00ebt","sequence":"first","affiliation":[]},{"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[]},{"given":"David","family":"Garc\u00eda-Soriano","sequence":"additional","affiliation":[]},{"given":"Arie","family":"Matsliah","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,10]]},"reference":[{"key":"2765_CR1","doi-asserted-by":"crossref","unstructured":"Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert D. Kleinberg and April Rasala Lehman: On the capacity of information networks, in: SODA, 241\u2013250, 2006.","DOI":"10.1145\/1109557.1109585"},{"issue":"11","key":"2765_CR2","doi-asserted-by":"crossref","first-page":"1704","DOI":"10.1016\/j.ic.2006.06.001","volume":"204","author":"N. Ailon","year":"2006","unstructured":"Nir Ailon and Bernard Chazelle: Information theory in property testing and monotonicity testing in higher dimension, Inf. Comput. 204(11) (2006), 1704\u20131717.","journal-title":"Inf. Comput."},{"key":"2765_CR3","doi-asserted-by":"crossref","unstructured":"Ali Al-Bashabsheh and Abbas Yonga\u00e7oglu: On the k-pairs problem, CoRR, abs\/0805.0050, 2008.","DOI":"10.1109\/ISIT.2008.4595304"},{"key":"2765_CR4","unstructured":"V. E. Benes: Mathematical theory of connecting networks and telephone traffic. New York, Academic Press, 1965."},{"key":"2765_CR5","unstructured":"Arnab Bhattacharyya: A note on the distance to monotonicity of boolean functions, Electronic Colloquium on Computational Complexity (ECCC) 15(012), 2008."},{"key":"2765_CR6","doi-asserted-by":"crossref","unstructured":"Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff: Transitive-closure spanners, in: SODA\u2019 09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, 932\u2013941, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973068.101"},{"key":"2765_CR7","doi-asserted-by":"crossref","unstructured":"Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff: Transitive-closure spanners of the hypercube and the hypergrid. Electronic Colloquium on Computational Complexity (ECCC) 09(046), 2009.","DOI":"10.1137\/1.9781611973068.101"},{"key":"2765_CR8","doi-asserted-by":"crossref","unstructured":"Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky: Improved testing algorithms for monotonicity, in: RANDOM-APPROX, 97\u2013108, 1999.","DOI":"10.1007\/978-3-540-48413-4_10"},{"issue":"3","key":"2765_CR9","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Erg\u00fcn","year":"2000","unstructured":"Funda Erg\u00fcn, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld and Mahesh Viswanathan: Spot-checkers, J. Comput. Syst. Sci. 60(3) (2000), 717\u2013751.","journal-title":"J. Comput. Syst. Sci."},{"key":"2765_CR10","unstructured":"Kevin Matulef Eric Blais, Joshua Brody: Property testing via communication complexity, To appear in Proc. CCC 2011, 2011."},{"issue":"1","key":"2765_CR11","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.ic.2003.09.003","volume":"189","author":"E. Fischer","year":"2004","unstructured":"Eldar Fischer: On the strength of comparisons in property testing, Inf. Comput. 189(1) (2004), 107\u2013116.","journal-title":"Inf. Comput."},{"key":"2765_CR12","doi-asserted-by":"crossref","unstructured":"Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky: Monotonicity testing over general poset domains, in: STOC, 474\u2013483, 2002.","DOI":"10.1145\/509973.509977"},{"key":"2765_CR13","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser, Eric Lehman and Dana Ron: Testing monotonicity, in: FOCS, 426\u2013435, 1998.","DOI":"10.1109\/SFCS.1998.743493"},{"issue":"3","key":"2765_CR14","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron and Alex Samorodnitsky: Testing monotonicity, Combinatorica 20(3) (2000), 301\u2013337.","journal-title":"Combinatorica"},{"issue":"1","key":"2765_CR15","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1002\/rsa.20211","volume":"33","author":"S. Halevy","year":"2008","unstructured":"Shirley Halevy and Eyal Kushilevitz: Testing monotonicity over graph products, Random Struct. Algorithms 33(1) (2008), 44\u201367.","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"2765_CR16","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1006\/jcta.2000.3148","volume":"94","author":"E. Lehman","year":"2001","unstructured":"Eric Lehman and Dana Ron: On disjoint chains of subsets, J. Comb. Theory, Ser. A 94(2) (2001), 399\u2013404.","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"2","key":"2765_CR17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(90)90106-8","volume":"35","author":"A. Lubiw","year":"1990","unstructured":"Anna Lubiw: Counterexample to a conjecture of szymanski on hypercube routing, Inf. Process. Lett. 35(2) (1990), 57\u201361.","journal-title":"Inf. Process. Lett."},{"key":"2765_CR18","volume-title":"Network coding","author":"A. Rasala-Lehman","year":"2005","unstructured":"A. Rasala-Lehman: Network coding, PhD thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 2005."},{"key":"2765_CR19","volume-title":"Monotonicity testing","author":"S. Raskhodnikova","year":"1999","unstructured":"Sofya Raskhodnikova: Monotonicity testing, Master\u2019s thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, 1999."},{"key":"2765_CR20","unstructured":"Ted H. Szymanski: On the permutation capability of a circuit-switched hypercube, in: ICPP (1), 103\u2013110, 1989."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2765-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-012-2765-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-012-2765-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T06:22:18Z","timestamp":1742451738000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-012-2765-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["2765"],"URL":"https:\/\/doi.org\/10.1007\/s00493-012-2765-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}