{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:40:06Z","timestamp":1741448406983,"version":"3.38.0"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_56","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"664-675","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the Influence of Monotone Boolean Functions in $O(\\sqrt{n})$ Query Complexity"],"prefix":"10.1007","author":[{"given":"Dana","family":"Ron","sequence":"first","affiliation":[]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[]},{"given":"Muli","family":"Safra","sequence":"additional","affiliation":[]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1086\/256963","volume":"58","author":"K. Arrow","year":"1950","unstructured":"Arrow, K.: A difficulty in the theory of social welfare. Journal of Political Economics\u00a058, 328\u2013346 (1950)","journal-title":"Journal of Political Economics"},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Linial, N.: Collective coin flipping, robust voting schemes and minima of Banzhaf values. In: Proceedings of FOCS, pp. 408\u2013416 (1985)","DOI":"10.1109\/SFCS.1985.15"},{"key":"56_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF02698830","volume":"90","author":"I. Benjamini","year":"1999","unstructured":"Benjamini, I., Kalai, G., Schramm, O.: Noise sensitivity of boolean functions and applications to percolation. Inst. Hautes Etudes Sci. Publ. Math.\u00a090, 5\u201343 (1999)","journal-title":"Inst. Hautes Etudes Sci. Publ. Math."},{"key":"56_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-540-85363-3_26","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Blais","year":"2008","unstructured":"Blais, E.: Improved bounds for testing juntas. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 317\u2013330. Springer, Heidelberg (2008)"},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"Blais, E.: Testing juntas nearly optimally. In: Proceedings of STOC, pp. 151\u2013158 (2009)","DOI":"10.1145\/1536414.1536437"},{"issue":"4","key":"56_CR6","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1145\/234533.234564","volume":"43","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Tamon, C.: On the Fourier spectrum of monotone functions. Journal of the ACM\u00a043(4), 747\u2013770 (1996)","journal-title":"Journal of the ACM"},{"key":"56_CR7","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of the Mathematical Statistics\u00a023, 493\u2013507 (1952)","journal-title":"Annals of the Mathematical Statistics"},{"key":"56_CR8","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Harsha, P., Klivans, A., Meka, R., Raghavendra, P., Servedio, R., Tan, L.-Y.: Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. In: Proceedings of STOC, pp. 533\u2013543 (2010)","DOI":"10.1145\/1806689.1806763"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: The importance of being biased. In: Proceedings of STOC, pp. 33\u201342 (2002)","DOI":"10.1145\/509907.509915"},{"issue":"4","key":"56_CR10","doi-asserted-by":"publisher","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, S.: Testing juntas. Journal of Computer and System Sciences\u00a068(4), 753\u2013787 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"56_CR11","unstructured":"Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124, 2993\u20133002 (1996)"},{"key":"56_CR12","unstructured":"Kalai, G., Safra, S.: Threshold phenomena and influence. In: Computational Complexity and Statistical Physics, pp. 25\u201360 (2006)"},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"Hancock, T., Mansour, Y.: Learning monotone k-\u03bc DNF formulas on product distributions. In: Proceedings of COLT, pp. 179\u2013183 (1991)","DOI":"10.1016\/B978-1-55860-213-7.50020-1"},{"key":"56_CR14","series-title":"Lectures in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating: algorithms and complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, Sampling and Integrating: algorithms and complexity. Lectures in Mathematics. ETH Z\u00fcrich, Birkh\u00e4user, Basel (2003)"},{"key":"56_CR15","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/S0196-8858(02)00023-4","volume":"29","author":"G. Kalai","year":"2002","unstructured":"Kalai, G.: A Fourier-theoretic perspective for the Condorcet Paradox and Arrow\u2019s Theorem. Advances in Applied Mathematics\u00a029, 412\u2013426 (2002)","journal-title":"Advances in Applied Mathematics"},{"key":"56_CR16","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1111\/j.1468-0262.2004.00543.x","volume":"72","author":"G. Kalai","year":"2004","unstructured":"Kalai, G.: Social indeterminacy. Econometrica\u00a072, 1565\u20131581 (2004)","journal-title":"Econometrica"},{"key":"56_CR17","doi-asserted-by":"crossref","unstructured":"Kalai, G., Kahn, J., Linial, N.: The influence of variables on Boolean functions. In: Proceedings of FOCS, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"56_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"key":"56_CR19","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1017\/S0963548302005199","volume":"11","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M., Sudakov, B., Vu, V.H.: A sharp threshold for network reliability. Combinatorics, Probability and Computing\u00a011, 465\u2013474 (2002)","journal-title":"Combinatorics, Probability and Computing"},{"key":"56_CR20","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01254541","volume":"17","author":"E. Lehrer","year":"1988","unstructured":"Lehrer, E.: An axiomatization of the Banzhaf value. International Journal of Game Theory\u00a017, 89\u201399 (1988)","journal-title":"International Journal of Game Theory"},{"issue":"3","key":"56_CR21","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. Journal of the ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"Journal of the ACM"},{"key":"56_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/978-3-642-03685-9_48","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Matulef","year":"2009","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.A.: Testing {\u2009\u2212\u20091,\u2009+\u20091} halfspaces. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 646\u2013657. Springer, Heidelberg (2009)"},{"key":"56_CR23","unstructured":"Matulef, K., Servedio, R., Wimmer, K.: Personal communication (2009)"},{"issue":"3","key":"56_CR24","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/060669309","volume":"37","author":"R. O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Servedio, R.: Learning monotone decision trees in polynomial time. SIAM Journal on Computing\u00a037(3), 827\u2013844 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"56_CR25","doi-asserted-by":"crossref","unstructured":"Ron, D., Rubinfeld, R., Safra, M., Weinstein, O.: Approximating the influence of a monotone boolean function in $o(\\sqrt{n})$ query complexity. Technical report, arXiv:1101.5345 (2011)","DOI":"10.1145\/2382559.2382562"},{"key":"56_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1007\/978-3-642-03685-9_51","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Ron","year":"2009","unstructured":"Ron, D., Tsur, G.: Testing computability by width two oBDDs. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 686\u2013699. Springer, Heidelberg (2009)"},{"key":"56_CR27","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF00535742","volume":"56","author":"L. Russo","year":"1981","unstructured":"Russo, L.: On the critical percolation probabilities. Z. Wahrsch. Verw. Geb.\u00a056, 229\u2013237 (1981)","journal-title":"Z. Wahrsch. Verw. Geb."},{"key":"56_CR28","doi-asserted-by":"publisher","first-page":"1576","DOI":"10.1214\/aop\/1176988612","volume":"22","author":"M. Talagrand","year":"1994","unstructured":"Talagrand, M.: On Russo\u2019s approximate 0\u2009\u2212\u20091 law. Annals of Probability\u00a022, 1576\u20131587 (1994)","journal-title":"Annals of Probability"}],"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-22935-0_56","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,8]],"date-time":"2025-03-08T15:18:15Z","timestamp":1741447095000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}