{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:40:37Z","timestamp":1776127237390,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T00:00:00Z","timestamp":1427241600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,3]]},"DOI":"10.1007\/s00453-015-9984-y","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T16:17:49Z","timestamp":1427213869000},"page":"1055-1081","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Testing Lipschitz Functions on Hypergrid Domains"],"prefix":"10.1007","volume":"74","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhav","family":"Jha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"issue":"3","key":"9984_CR1","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1002\/rsa.20167","volume":"31","author":"N Ailon","year":"2007","unstructured":"Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone function. Random Struct. Algorithm. 31(3), 371\u2013383 (2007)","journal-title":"Random Struct. Algorithm."},{"key":"9984_CR2","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Jha, M., Molinaro, M., Raskhodnikova, S..: Testing Lipschitz functions on hypergrid domains. Proceedings of APPROX-RANDOM, pp. 387\u2013398 (2012)","DOI":"10.1007\/978-3-642-32512-0_33"},{"issue":"6","key":"9984_CR3","doi-asserted-by":"crossref","first-page":"1380","DOI":"10.1137\/110826655","volume":"41","author":"A Bhattacharyya","year":"2012","unstructured":"Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.P.: Transitive-closure spanners. SIAM J. Comput. 41(6), 1380\u20131425 (2012)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9984_CR4","doi-asserted-by":"crossref","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. 47(3), 549\u2013595 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9984_CR5","doi-asserted-by":"crossref","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. Inf. Comput. 196(1), 42\u201356 (2005)","journal-title":"Inf. Comput."},{"key":"9984_CR6","doi-asserted-by":"crossref","unstructured":"Berman, P., Raskhodnikova, S., Yaroslavtsev, G.: $$L_p$$ L p -testing. In: Proceedings of the 46th Symposium on Theory of Computing, STOC , pp. 164\u2013173 (2014)","DOI":"10.1145\/2591796.2591887"},{"key":"9984_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Dixit, K., Jha, M., Seshadhri, C.: Property testing on product distributions: optimal testers for bounded derivative properties. In Proceedings of the 26th Symposium on Discrete Algorithms, SODA, pp. 1809\u20131828 (2015)","DOI":"10.1137\/1.9781611973730.121"},{"key":"9984_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. In: Property Testing, Lecture Notes in Computer Science 6390, pp. 41\u201364. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-16367-8_5"},{"key":"9984_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Seshadhri, C.: Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In: Proceedings of the 45th Symposium on Theory of Computing, STOC, pp. 419\u2013428 (2013)","DOI":"10.1145\/2488608.2488661"},{"key":"9984_CR10","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Proceedings of APPROX-RANDOM , pp. 97\u2013108 (1999)","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"9984_CR11","doi-asserted-by":"crossref","unstructured":"Dixit, K., Jha, M., Raskhodnikova, S., Thakurta, A.: Testing the Lipschitz property over product distributions with applications to data privacy. In: Proceedings of the 10th Theory of Cryptography Conference, TCC, pp. 418\u2013436 (2013)","DOI":"10.1007\/978-3-642-36594-2_24"},{"issue":"3","key":"9984_CR12","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1006\/jcss.1999.1692","volume":"60","author":"F Ergun","year":"2000","unstructured":"Ergun, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci. 60(3), 717\u2013751 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9984_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: Proceedings of the 34th Symposium on Theory of Computing, STOC, pp. 474\u2013483 (2002)","DOI":"10.1145\/509907.509977"},{"issue":"3","key":"9984_CR14","doi-asserted-by":"crossref","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 20(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"4","key":"9984_CR15","doi-asserted-by":"crossref","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 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"9984_CR16","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Introduction to testing graph properties. In Studies in Complexity and Cryptography, Lecture Notes in Computer Science 6390, pp. 470\u2013506. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22670-0_32"},{"key":"9984_CR17","unstructured":"Gromov, M.: Metric Structures for Riemannian and non-Riemannian Spaces. Birkhauser, Switzerland (1999)"},{"issue":"1","key":"9984_CR18","doi-asserted-by":"crossref","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. Algorithm. 33(1), 44\u201367 (2008)","journal-title":"Random Struct. Algorithm."},{"issue":"2","key":"9984_CR19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/rsa.20262","volume":"35","author":"CS Jutla","year":"2009","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. Random Struct. Algorithm. 35(2), 163\u2013193 (2009)","journal-title":"Random Struct. Algorithm."},{"issue":"2","key":"9984_CR20","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1137\/110840741","volume":"42","author":"M Jha","year":"2013","unstructured":"Jha, M., Raskhodnikova, S.: Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM J. Comput. 42(2), 700\u2013731 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9984_CR21","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"36","author":"T Kaufman","year":"2006","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM J. Comput. 36(3), 779\u2013802 (2006)","journal-title":"SIAM J. Comput."},{"key":"9984_CR22","first-page":"148","volume":"141","author":"C McDiarmid","year":"1989","unstructured":"McDiarmid, C.: On the method of bounded differences. Surv. Comb. Lond. Math. Soc. Lecture Note 141, 148\u2013188 (1989)","journal-title":"Surv. Comb. Lond. Math. Soc. Lecture Note"},{"issue":"3","key":"9984_CR23","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1016\/j.jfa.2008.11.001","volume":"256","author":"Y Ollivier","year":"2009","unstructured":"Ollivier, Y.: Ricci curvature of Markov chains on metric spaces. J. Funct. Anal. 256(3), 810\u2013864 (2009)","journal-title":"J. Funct. Anal."},{"issue":"2","key":"9984_CR24","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D Ron","year":"2009","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trend Theor. Comput. Sci. 5(2), 73\u2013205 (2009)","journal-title":"Found. Trend Theor. Comput. Sci."},{"issue":"2","key":"9984_CR25","doi-asserted-by":"crossref","first-page":"252","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 J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9984_CR26","doi-asserted-by":"crossref","first-page":"1562","DOI":"10.1137\/100791075","volume":"25","author":"R Rubinfeld","year":"2011","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. SIAM J. Discret. Math. 25(4), 1562\u20131588 (2011)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9984_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-012-9719-2","volume":"69","author":"C Seshadhri","year":"2014","unstructured":"Seshadhri, C., Vondr\u00e1k, J.: Is submodularity testable? Algorithmica 69(1), 1\u201325 (2014)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9984-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9984-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9984-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T06:27:15Z","timestamp":1566455235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9984-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["9984"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9984-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,25]]}}}