{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:51:35Z","timestamp":1744217495207},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,19]],"date-time":"2013-12-19T00:00:00Z","timestamp":1387411200000},"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":[[2015,6]]},"DOI":"10.1007\/s00453-013-9858-0","type":"journal-article","created":{"date-parts":[[2013,12,18]],"date-time":"2013-12-18T11:51:57Z","timestamp":1387367517000},"page":"400-429","source":"Crossref","is-referenced-by-count":1,"title":["Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities"],"prefix":"10.1007","volume":"72","author":[{"given":"Dana","family":"Ron","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,12,19]]},"reference":[{"issue":"11","key":"9858_CR1","doi-asserted-by":"crossref","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. 204(11), 1704\u20131717 (2006)","journal-title":"Inf. Comput."},{"issue":"11","key":"9858_CR2","doi-asserted-by":"crossref","first-page":"4032","DOI":"10.1109\/TIT.2005.856958","volume":"51","author":"N. Alon","year":"2005","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing Reed-Muller codes. IEEE Trans. Inf. Theory 51(11), 4032\u20134039 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9858_CR3","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/978-3-540-85363-3_26","volume-title":"Proceedings of the 12th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM)","author":"E. Blais","year":"2008","unstructured":"Blais, E.: Improved bounds for testing juntas. In: Proceedings of the 12th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM), pp. 317\u2013330 (2008)"},{"key":"9858_CR4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/1536414.1536437","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC)","author":"E. Blais","year":"2009","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 151\u2013158 (2009)"},{"key":"9858_CR5","first-page":"235","volume-title":"Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC)","author":"E. Blais","year":"2010","unstructured":"Blais, E., O\u2019Donnell, R.: Lower bounds for testing function isomorphism. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pp. 235\u2013246 (2010)"},{"issue":"3","key":"9858_CR6","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":"9858_CR7","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(1), 35\u201353 (2012)","journal-title":"Combinatorica"},{"key":"9858_CR8","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/978-3-642-20877-5_32","volume-title":"Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC)","author":"J. Brody","year":"2011","unstructured":"Brody, J., Matulef, K., Wu, C.: Lower bounds for testing computability by small width OBDDs. In: Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC), pp. 320\u2013331 (2011)"},{"key":"9858_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.gs.2008.001","volume":"1","author":"R. Wolf de","year":"2008","unstructured":"de Wolf, R.: A brief introduction to Fourier analysis on the boolean cube. Theory Comput. 1, 1\u201320 (2008)","journal-title":"Theory Comput."},{"key":"9858_CR10","first-page":"549","volume-title":"Proceedings of the 48th Annual Symposium on Computer Science (FOCS)","author":"I. Diakonikolas","year":"2007","unstructured":"Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., Wan, A.: Testing for concise representations. In: Proceedings of the 48th Annual Symposium on Computer Science (FOCS), pp. 549\u2013558 (2007)"},{"key":"9858_CR11","first-page":"97","volume-title":"Proceedings of the Third 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 Third International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pp. 97\u2013108 (1999)"},{"key":"9858_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"9858_CR13","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":"4","key":"9858_CR14","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/j.jcss.2003.11.004","volume":"68","author":"E. Fischer","year":"2004","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. J. Comput. Syst. Sci. 68(4), 753\u2013787 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"9858_CR15","first-page":"474","volume-title":"Proceedings of the 34th Annual ACM 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 ACM Symposium on Theory of Computing (STOC), pp. 474\u2013483 (2002)"},{"key":"9858_CR16","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1007\/978-3-642-15369-3_43","volume-title":"Proceedings of the 14th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM)","author":"O. Goldreich","year":"2010","unstructured":"Goldreich, O.: On testing computability by small width OBDDs. In: Proceedings of the 14th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM), pp. 574\u2013587 (2010)"},{"key":"9858_CR17","series-title":"LNCS","volume-title":"Property Testing: Current Research and Surveys","year":"2010","unstructured":"Goldreich, O. (ed.): Property Testing: Current Research and Surveys. LNCS, vol. 6390. Springer, Berlin (2010)"},{"issue":"3","key":"9858_CR18","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(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"issue":"4","key":"9858_CR19","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"},{"issue":"4","key":"9858_CR20","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1137\/100785429","volume":"40","author":"P. Gopalan","year":"2011","unstructured":"Gopalan, P., O\u2019Donnell, R., Servedio, R., Shpilka, A., Wimmer, K.: Testing Fourier dimensionality and sparsity. SIAM J. Comput. 40(4), 1075\u20131100 (2011)","journal-title":"SIAM J. Comput."},{"key":"9858_CR21","first-page":"223","volume-title":"Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC)","author":"P. Gopalan","year":"2010","unstructured":"Gopalan, P., O\u2019Donnell, R., Wu, Y., Zuckerman, D.: Fooling functions of halfspaces under product distributions. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pp. 223\u2013234 (2010)"},{"issue":"1","key":"9858_CR22","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. Algorithms 33(1), 44\u201367 (2008)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"9858_CR23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1002\/rsa.20262","volume":"35","author":"C.S. Jutla","year":"2009","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. Random Struct. Algorithms 35(2), 163\u2013193 (2009)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"9858_CR24","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1137\/S0097539704445615","volume":"35","author":"T. Kaufman","year":"2006","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM J. Comput. 35(3), 779\u2013802 (2006)","journal-title":"SIAM J. Comput."},{"key":"9858_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1515\/crll.1999.511.1","volume":"511","author":"H. K\u00f6nig","year":"1999","unstructured":"K\u00f6nig, H., Sch\u00fctt, C., Tomczak-Jaegermann, N.: Projection constants of symmetric spaces and variants of Khintchine\u2019s inequality. J. Reine Angew. Math. 511, 1\u201342 (1999)","journal-title":"J. Reine Angew. Math."},{"issue":"5","key":"9858_CR26","doi-asserted-by":"crossref","first-page":"2004","DOI":"10.1137\/070707890","volume":"39","author":"K. Matulef","year":"2010","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.: Testing halfspaces. SIAM J. Comput. 39(5), 2004\u20132047 (2010)","journal-title":"SIAM J. Comput."},{"key":"9858_CR27","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1007\/978-3-642-03685-9_48","volume-title":"Proceedings of the 13th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM)","author":"K. Matulef","year":"2009","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.A.: Testing \u00b11-weight halfspaces. In: Proceedings of the 13th International Workshop on Approximation, Randomization and Combinatorial Optimization (RANDOM), pp. 646\u2013657 (2009)"},{"key":"9858_CR28","first-page":"156","volume-title":"Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"E. Mossel","year":"2008","unstructured":"Mossel, E.: Gaussian bounds for noise correlation of functions and tight analysis of long codes. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 156\u2013165 (2008)"},{"key":"9858_CR29","first-page":"569","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC)","author":"R. O\u2019Donnell","year":"2008","unstructured":"O\u2019Donnell, R.: Some topics in analysis of Boolean functions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 569\u2013578 (2008)"},{"issue":"1","key":"9858_CR30","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic Boolean formulae. SIAM J. Discrete Math. 16(1), 20\u201346 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9858_CR31","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1561\/2200000004","volume":"1","author":"D. Ron","year":"2008","unstructured":"Ron, D.: Property testing: a learning theory perspective. Found. Trends Mach. Learn. 1(3), 307\u2013402 (2008)","journal-title":"Found. Trends Mach. Learn."},{"issue":"2","key":"9858_CR32","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1561\/0400000029","volume":"5","author":"D. Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5(2), 73\u2013205 (2010)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"9858_CR33","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.tcs.2011.11.007","volume":"420","author":"D. Ron","year":"2012","unstructured":"Ron, D., Tsur, G.: Testing computability by width-two OBDDs. Theor. Comput. Sci. 420, 64\u201379 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9858_CR34","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01121471","volume":"35","author":"I.S. Shiganov","year":"1986","unstructured":"Shiganov, I.S.: Refinement of the upper bound of a constant in the remainder term of the central limit theorem. J. Sov. Math. 35(3), 109\u2013115 (1986)","journal-title":"J. Sov. Math."},{"key":"9858_CR35","unstructured":"Wikipedia contributors. Central binomial coefficient. Wikipedia, The Free Encyclopedia, accessed June\u00a08 (2012). http:\/\/en.wikipedia.org\/wiki\/Central_binomial_coefficient"},{"key":"9858_CR36","first-page":"222","volume-title":"Proceedings of the Seventeenth Annual Symposium on Foundations of Computer Science (STOC)","author":"A. Yao","year":"1977","unstructured":"Yao, A.: Probabilistic computations: towards a unified measure of complexity. In: Proceedings of the Seventeenth Annual Symposium on Foundations of Computer Science (STOC), pp. 222\u2013227 (1977)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9858-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9858-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9858-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:13Z","timestamp":1559123113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9858-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,19]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9858"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9858-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,19]]}}}