{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T06:38:57Z","timestamp":1784097537779,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,11,21]],"date-time":"2012-11-21T00:00:00Z","timestamp":1353456000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,5]]},"DOI":"10.1007\/s00453-012-9719-2","type":"journal-article","created":{"date-parts":[[2012,11,20]],"date-time":"2012-11-20T05:50:17Z","timestamp":1353390617000},"page":"1-25","source":"Crossref","is-referenced-by-count":14,"title":["Is Submodularity Testable?"],"prefix":"10.1007","volume":"69","author":[{"given":"C.","family":"Seshadhri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,11,21]]},"reference":[{"key":"9719_CR1","first-page":"210","volume-title":"Proceedings of the 26th Conference on Computational Complexity (CCC)","author":"E. Blais","year":"2011","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. In: Proceedings of the 26th Conference on Computational Complexity (CCC), pp. 210\u2013220 (2011)"},{"key":"9719_CR2","doi-asserted-by":"crossref","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 32, 35\u201353 (2012). Conference version in RANDOM 2010","journal-title":"Combinatorica"},{"issue":"1","key":"9719_CR3","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/S0097539702403645","volume":"35","author":"T. Batu","year":"2005","unstructured":"Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R.: The complexity of approximating the entropy. SIAM J. Comput. 35(1), 132\u2013150 (2005)","journal-title":"SIAM J. Comput."},{"key":"9719_CR4","first-page":"239","volume-title":"Proceedings of Innovations in Computer Science (ICS)","author":"A. Bhattacharyya","year":"2011","unstructured":"Bhattacharyya, A., Fischer, E., Rubinfeld, R., Valiant, P.: Testing monotonicity of distributions over general partial orders. In: Proceedings of Innovations in Computer Science (ICS), pp. 239\u2013252 (2011)"},{"key":"9719_CR5","first-page":"793","volume-title":"Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC)","author":"M.-F. Balcan","year":"2011","unstructured":"Balcan, M.-F., Harvey, N.: Learning submodular functions. In: Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC), pp. 793\u2013802 (2011)"},{"key":"9719_CR6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/978-3-642-31594-7_15","volume-title":"Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"D. Chakrabarty","year":"2012","unstructured":"Chakrabarty, D., Huang, Z.: Testing coverage functions. In: Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 170\u2013181 (2012)"},{"key":"9719_CR7","volume-title":"Proceedings of the 25th Annual Symposium on Discrete Algorithms (SODA)","author":"M. Cheraghchi","year":"2012","unstructured":"Cheraghchi, M., Klivans, A., Kothari, P., Lee, H.K.: Submodular functions are noise stable. In: Proceedings of the 25th Annual Symposium on Discrete Algorithms (SODA) (2012)"},{"key":"9719_CR8","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Seshadhri, C.: Optimal bounds for monotonicity and Lipschitz testing over the hypercube. Technical Report TR12-030, ECCC (2012)","DOI":"10.1145\/2488608.2488661"},{"key":"9719_CR9","first-page":"97","volume-title":"Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pp. 97\u2013108 (1999)"},{"key":"9719_CR10","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J.: Matroids, submodular functions and certain polyhedra. In: Combinatorial Structures and Their Applications, pp. 69\u201387 (1970)"},{"key":"9719_CR11","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: a primer to property testing. Bull. Eur. Assoc. Theor. Comput. Sci. 75, 97\u2013126 (2001)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"1","key":"9719_CR12","doi-asserted-by":"crossref","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. 189(1), 107\u2013116 (2004)","journal-title":"Inf. Comput."},{"key":"9719_CR13","first-page":"474","volume-title":"Proceedings of the 34th Annual Symposium on Theory of Computing (STOC)","author":"E. Fischer","year":"2002","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 Symposium on Theory of Computing (STOC), pp. 474\u2013483 (2002)"},{"key":"9719_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M.L. Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions ii. Math. Program. Stud. 8, 73\u201387 (1978)","journal-title":"Math. Program. Stud."},{"key":"9719_CR15","unstructured":"Fattal, S., Ron, D.: Approximating the distance to monotonicity in high dimensions. http:\/\/www.eng.tau.ac.il\/~danar\/Public-pdf\/app-mon-long.pdf"},{"key":"9719_CR16","first-page":"65","volume-title":"Annotated Biblographies in Combinatorial Optimization","author":"A. Frank","year":"1997","unstructured":"Frank, A.: Matroids and submodular functions. In: Annotated Biblographies in Combinatorial Optimization, pp.\u00a065\u201380 (1997)"},{"key":"9719_CR17","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., Samordinsky, A.: Testing monotonicity. Combinatorica 20, 301\u2013337 (2000). Conference Version in FOCS 1998","journal-title":"Combinatorica"},{"issue":"4","key":"9719_CR18","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). Conference version in FOCS 1996","journal-title":"J. ACM"},{"key":"9719_CR19","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1137\/1.9781611973068.59","volume-title":"Proceedings of 22th Annual Symposium on Discrete Algorithms (SODA)","author":"M. Goemans","year":"2009","unstructured":"Goemans, M., Harvey, N., Iwata, S., Mirrokni, V.: Approximating submodular functions everywhere. In: Proceedings of 22th Annual Symposium on Discrete Algorithms (SODA), pp. 535\u2013544 (2009)"},{"key":"9719_CR20","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1002\/j.1538-7305.1958.tb03887.x","volume":"37","author":"E.N. Gilbert","year":"1958","unstructured":"Gilbert, E.N.: Gray codes and paths on the n-cube. Bell Syst. Tech. J. 37, 815\u2013826 (1958)","journal-title":"Bell Syst. Tech. J."},{"key":"9719_CR21","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1090\/dimacs\/043\/04","volume-title":"Randomization Methods in Algorithm Design","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O.: Combinatorial property testing\u2014a survey. In: Randomization Methods in Algorithm Design, pp.\u00a045\u201360 (1998)"},{"key":"9719_CR22","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM 48, 4 (2001). Conference version in STOC 2000","journal-title":"J. ACM"},{"key":"9719_CR23","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming: the State of the Art","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming: the State of the Art, pp. 235\u2013257 (1983)"},{"key":"9719_CR24","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions i. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"5","key":"9719_CR25","doi-asserted-by":"crossref","first-page":"1158","DOI":"10.1137\/S0097539702414026","volume":"32","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: On testing convexity and submodularity. SIAM J. Comput. 32(5), 1158\u20131184 (2003). Conference version in RANDOM 2002","journal-title":"SIAM J. Comput."},{"key":"9719_CR26","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume-title":"Handbook on Randomization","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing. In: Handbook on Randomization, vol.\u00a0II, pp.\u00a0597\u2013649 (2001)"},{"key":"9719_CR27","doi-asserted-by":"crossref","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 J. Comput. 25, 647\u2013668 (1996)","journal-title":"SIAM J. Comput."},{"key":"9719_CR28","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory, Ser. B 80, 346\u2013355 (2000)","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9719-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9719-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9719-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T21:49:59Z","timestamp":1687816199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9719-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,21]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["9719"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9719-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,21]]}}}