{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:35:19Z","timestamp":1787506519610,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642403279","type":"print"},{"value":"9783642403286","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_30","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"425-435","source":"Crossref","is-referenced-by-count":10,"title":["An Optimal Lower Bound for Monotonicity Testing over Hypergrids"],"prefix":"10.1007","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal of Computing\u00a025, 647\u2013668 (1996)","journal-title":"SIAM Journal of Computing"},{"issue":"4","key":"30_CR2","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. Journal of the ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"key":"30_CR3","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, 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"3","key":"30_CR4","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F. Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. Journal of Computer Systems and Sciences (JCSS)\u00a060(3), 717\u2013751 (2000)","journal-title":"Journal of Computer Systems and Sciences (JCSS)"},{"key":"30_CR5","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-APPROX 1999. LNCS, vol.\u00a01671, pp. 97\u2013108. Springer, Heidelberg (1999)"},{"issue":"2","key":"30_CR6","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. Journal of Combinatorial Theory, Series A\u00a094(2), 399\u2013404 (2001)","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing (STOC), pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"11","key":"30_CR8","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. Information and Computation\u00a0204(11), 1704\u20131717 (2006)","journal-title":"Information and Computation"},{"issue":"1","key":"30_CR9","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. Information and Computation\u00a0189(1), 107\u2013116 (2004)","journal-title":"Information and Computation"},{"issue":"1","key":"30_CR10","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 Structures and Algorithms\u00a033(1), 44\u201367 (2008)","journal-title":"Random Structures and Algorithms"},{"issue":"6","key":"30_CR11","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"72","author":"M. Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. Journal of Computer and System Sciences\u00a072(6), 1012\u20131042 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"30_CR12","first-page":"1704","volume":"31","author":"N. Ailon","year":"2006","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone function. Random Structures and Algorithms\u00a031(3), 1704\u20131711 (2006)","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"30_CR13","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.ic.2004.10.001","volume":"196","author":"T. Batu","year":"2005","unstructured":"Batu, T., Rubinfeld, R., White, P.: Fast approximate PCPs for multidimensional bin-packing problems. Information and Computation\u00a0196(1), 42\u201356 (2005)","journal-title":"Information and Computation"},{"issue":"2","key":"30_CR14","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00037-012-0040-x","volume":"21","author":"E. Blais","year":"2012","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. Computational Complexity\u00a021(2), 311\u2013358 (2012)","journal-title":"Computational Complexity"},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Seshadhri, C.: Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In: Proceedings of Symposium on Theory of Computing, STOC (2013)","DOI":"10.1145\/2488608.2488661"},{"key":"30_CR16","unstructured":"Brody, J.: Personal communication (2013)"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Blais, E., Raskhodnikova, S., Yaroslavtsev, G.: Lower bounds for testing properties of functions on hypergrid domains. Technical Report TR13-036, ECCC (March 2013)","DOI":"10.1109\/CCC.2014.38"},{"issue":"1","key":"30_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s00493-012-2765-1","volume":"32","author":"J. Bri\u00ebt","year":"2012","unstructured":"Bri\u00ebt, J., Chakraborty, S., Garc\u00eda-Soriano, D., Matsliah, A.: Monotonicity testing and shortest-path routing on the cube. Combinatorica\u00a032(1), 35\u201353 (2012)","journal-title":"Combinatorica"},{"key":"30_CR19","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer (2000)"}],"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-40328-6_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:42:32Z","timestamp":1558014152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}