{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T19:21:55Z","timestamp":1769628115960,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2011,11,1]],"date-time":"2011-11-01T00:00:00Z","timestamp":1320105600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2011,11]]},"DOI":"10.1007\/s00493-011-2580-0","type":"journal-article","created":{"date-parts":[[2011,11,23]],"date-time":"2011-11-23T07:16:49Z","timestamp":1322032609000},"page":"583-614","source":"Crossref","is-referenced-by-count":14,"title":["The unbounded-error communication complexity of symmetric functions"],"prefix":"10.1007","volume":"31","author":[{"given":"Alexander A.","family":"Sherstov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,23]]},"reference":[{"key":"2580_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Frankl and V. R\u00f6dl: Geometrical realization of set systems and probabilistic communication complexity, in Proc. of the 26th Symposium on Foundations of Computer Science (FOCS), 277\u2013280, 1985.","DOI":"10.1109\/SFCS.1985.30"},{"issue":"2","key":"2580_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BF01215346","volume":"14","author":"J. Aspnes","year":"1994","unstructured":"J. Aspnes, R. Beigel, M. L. Furst and S. Rudich: The expressive power of voting polynomials, Combinatorica 14(2) (1994), 135\u2013148.","journal-title":"Combinatorica"},{"key":"2580_CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl and J. Simon: Complexity classes in communication complexity theory, in Proc. of the 27th Symposium on Foundations of Computer Science (FOCS), 337\u2013347, 1986.","DOI":"10.1109\/SFCS.1986.15"},{"issue":"4","key":"2580_CR4","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z. Bar-Yossef","year":"2004","unstructured":"Z. Bar-Yossef, T. S. Jayram, R. Kumar and D. Sivakumar: An information statistics approach to data stream and communication complexity, J. Comput. Syst. Sci. 68(4) (2004) 702\u2013732.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR5","doi-asserted-by":"crossref","unstructured":"H. Buhrman, N. K. Vereshchagin and R. de Wolf: On computation and communication with small bias, in Proc. of the 22nd Conf. on Computational Complexity (CCC), 24\u201332, 2007.","DOI":"10.1109\/CCC.2007.18"},{"key":"2580_CR6","doi-asserted-by":"crossref","unstructured":"V. Feldman, P. Gopalan, S. Khot and A. K. Ponnuswami: New results for learning noisy parities and halfspaces, in Proceedings of the 47th Annual Symposium on Foundations of Computer Science (FOCS), 563\u2013574, 2006.","DOI":"10.1109\/FOCS.2006.51"},{"issue":"4","key":"2580_CR7","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1016\/S0022-0000(02)00019-3","volume":"65","author":"J. Forster","year":"2002","unstructured":"J. Forster: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci., 65(4) (2002), 612\u2013625.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR8","doi-asserted-by":"crossref","unstructured":"J. Forster, M. Krause, S. V. Lokam, R. Mubarakzjanov, N. Schmitt and H.-U. Simon: Relations between communication complexity, linear arrangements computational complexity, in Proc. of the 21st Conf. on Foundations of Software Technology and Theoretical Computer Science (FST TCS), 171\u2013182, 2001.","DOI":"10.1007\/3-540-45294-X_15"},{"issue":"1","key":"2580_CR9","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.tcs.2005.10.015","volume":"350","author":"J. Forster","year":"2006","unstructured":"J. Forster and H. U. Simon: On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes, Theor. Comput. Sci., 350(1) (2006), 40\u201348.","journal-title":"Theor. Comput. Sci."},{"key":"2580_CR10","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M. Goldmann","year":"1992","unstructured":"M. Goldmann, J. H\u00e5stad and A. A. Razborov: Majority gates vs. general weighted threshold gates, Computational Complexity, 2 (1992), 277\u2013300.","journal-title":"Computational Complexity"},{"issue":"2","key":"2580_CR11","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0022-0000(93)90001-D","volume":"46","author":"A. Hajnal","year":"1993","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy and G. Tur\u00e1n: Threshold circuits of bounded depth, J. Comput. Syst. Sci., 46(2) (1993), 129\u2013154.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal combinatorics with applications in computer science","author":"S. Jukna","year":"2001","unstructured":"S. Jukna: Extremal combinatorics with applications in computer science, Springer-Verlag, Berlin, 2001."},{"issue":"4","key":"2580_CR13","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"B. Kalyanasundaram and G. Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4) (1992), 545\u2013557.","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"2580_CR14","doi-asserted-by":"crossref","first-page":"535","DOI":"10.4213\/mzm1314","volume":"63","author":"B. S. Kashin","year":"1998","unstructured":"B. S. Kashin and A. A. Razborov: Improved lower bounds on the rigidity of Hadamard matrices, Matematicheskie zametki, 63(4) (1998), 535\u2013540. In Russian.","journal-title":"Matematicheskie zametki"},{"issue":"1","key":"2580_CR15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"M. Kearns and L. Valiant: Cryptographic limitations on learning Boolean formulae and finite automata, J. ACM, 41(1) (1994), 67\u201395.","journal-title":"J. ACM"},{"key":"2580_CR16","doi-asserted-by":"crossref","unstructured":"M. Kharitonov: Cryptographic hardness of distribution-specific learning, in Proc. of the 25th Symposium on Theory of Computing, 372\u2013381, 1993.","DOI":"10.1145\/167088.167197"},{"issue":"5","key":"2580_CR17","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1137\/05063235X","volume":"36","author":"H. Klauck","year":"2007","unstructured":"H. Klauck, R. \u0160palek and R. de Wolf: Quantum and classical strong direct product theorems and optimal time-space tradeoffs, SIAM J. Comput., 36(5) (2007), 1472\u20131493.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2580_CR18","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A. R. Klivans","year":"2004","unstructured":"A. R. Klivans and R. A. Servedio: Learning DNF in time $$2^{\\tilde O(n^{1\/3} )}$$ , J. Comput. Syst. Sci., 68(2) (2004), 303\u2013318.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR19","doi-asserted-by":"crossref","unstructured":"A. R. Klivans and A. A. Sherstov: A lower bound for agnostically learning disjunctions, in Proc. of the 20th Conf. on Learning Theory (COLT), 409\u2013423, 2007.","DOI":"10.1007\/978-3-540-72927-3_30"},{"issue":"2\u20133","key":"2580_CR20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10994-007-5010-1","volume":"69","author":"A. R. Klivans","year":"2007","unstructured":"A. R. Klivans and A. A. Sherstov: Unconditional lower bounds for learning intersections of halfspaces, Machine Learning, 69(2\u20133) (2007), 97\u2013114.","journal-title":"Machine Learning"},{"issue":"1","key":"2580_CR21","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.jcss.2008.07.008","volume":"75","author":"A. R. Klivans","year":"2009","unstructured":"A. R. Klivans and A. A. Sherstov: Cryptographic hardness for learning intersections of halfspaces, J. Comput. Syst. Sci., 75(1) (2009), 2\u201312.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR22","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"E. Kushilevitz and N. Nisan: Communication complexity, Cambridge University Press, New York, 1997."},{"issue":"3","key":"2580_CR23","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"S. V. Lokam","year":"2001","unstructured":"S. V. Lokam: Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity, J. Comput. Syst. Sci., 63(3) (2001), 449\u2013473.","journal-title":"J. Comput. Syst. Sci."},{"key":"2580_CR24","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"M. L. Minsky","year":"1969","unstructured":"M. L. Minsky and S. A. Papert: Perceptrons: An Introduction to Computational Geometry, MIT Press, Cambridge, Mass., 1969."},{"issue":"2","key":"2580_CR25","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"I. Newman: Private vs. common random bits in communication complexity, Inf. Process. Lett., 39(2) (1991), 67\u201371.","journal-title":"Inf. Process. Lett."},{"key":"2580_CR26","unstructured":"N. Nisan: The communication complexity of threshold gates, in Combinatorics, Paul Erd\u0151s is Eighty, 301\u2013315, 1993."},{"key":"2580_CR27","doi-asserted-by":"crossref","unstructured":"R. Paturi: On the degree of polynomials that approximate symmetric Boolean functions, in Proc. of the 24th Symposium on Theory of Computing (STOC), 468\u2013474, 1992.","DOI":"10.1145\/129712.129758"},{"issue":"1","key":"2580_CR28","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"R. Paturi","year":"1986","unstructured":"R. Paturi and J. Simon: Probabilistic communication complexity. J. Comput. Syst. Sci., 33(1) (1986), 106\u2013123.","journal-title":"J. Comput. Syst. Sci."},{"issue":"3\/4","key":"2580_CR29","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01206318","volume":"5","author":"R. Raz","year":"1995","unstructured":"R. Raz: Fourier analysis for probabilistic communication complexity, Comput. Complex., 5(3\/4) (1995), 205\u2013221.","journal-title":"Comput. Complex."},{"key":"2580_CR30","unstructured":"A. A. Razborov: Bounded-depth formulae over the basis {&,\u2295} and some combinatorial problems, Complexity Theory and Applied Mathematical Logic, vol. \u201cProblems of Cybernetics\u201d (1988), 146\u2013166. In Russian."},{"issue":"2","key":"2580_CR31","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A. A. Razborov","year":"1992","unstructured":"A. A. Razborov: On the distributional complexity of disjointness, Theor. Comput. Sci., 106(2) (1992), 385\u2013390.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"2580_CR32","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A. A. Razborov","year":"2003","unstructured":"A. A. Razborov: Quantum communication complexity of symmetric predicates, Izvestiya: Mathematics, 67(1) (2003), 145\u2013159.","journal-title":"Izvestiya: Mathematics"},{"key":"2580_CR33","doi-asserted-by":"crossref","unstructured":"A. A. Razborov and A. A. Sherstov: The sign-rank of AC0, in Proc. of the 49th Symposium on Foundations of Computer Science (FOCS), 57\u201366, 2008.","DOI":"10.1109\/FOCS.2008.19"},{"key":"2580_CR34","volume-title":"An Introduction to the Approximation of Functions","author":"T. J. Rivlin","year":"1981","unstructured":"T. J. Rivlin: An Introduction to the Approximation of Functions, Dover Publications, New York, 1981."},{"issue":"2\u20133","key":"2580_CR35","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.ipl.2006.11.003","volume":"102","author":"A. A. Sherstov","year":"2007","unstructured":"A. A. Sherstov: Powering requires threshold depth 3, Inf. Process. Lett., 102(2\u20133) (2007), 104\u2013107.","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"2580_CR36","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00037-008-0242-4","volume":"17","author":"A. A. Sherstov","year":"2008","unstructured":"A. A. Sherstov: Halfspace matrices. Comput. Complex., 17(2) (2008), 149\u2013178. Preliminary version in 22nd CCC, 2007.","journal-title":"Comput. Complex."},{"key":"2580_CR37","doi-asserted-by":"crossref","unstructured":"A. A. Sherstov: The pattern matrix method, SIAM J. Comput., 2010, To appear. Preliminary version in 40th STOC, 2008.","DOI":"10.1137\/080733644"},{"issue":"6","key":"2580_CR38","doi-asserted-by":"crossref","first-page":"2113","DOI":"10.1137\/08071421X","volume":"38","author":"A. A. Sherstov","year":"2009","unstructured":"A. A. Sherstov: Separating AC0 from depth-2 majority circuits, SIAM J. Comput., 38(6) (2009), 2113\u20132129. Preliminary version in 39th STOC, 2007.","journal-title":"SIAM J. Comput."},{"issue":"5\u20136","key":"2580_CR39","doi-asserted-by":"crossref","first-page":"444","DOI":"10.26421\/QIC9.5-6-7","volume":"9","author":"Y. Shi","year":"2009","unstructured":"Y. Shi and Y. Zhu: Quantum communication complexity of block-composed functions, Quantum Information & Computation, 9(5\u20136) (2009), 444\u2013460.","journal-title":"Quantum Information & Computation"},{"issue":"11","key":"2580_CR40","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant: A theory of the learnable, Commun. ACM, 27(11) (1984), 1134\u20131142.","journal-title":"Commun. ACM"},{"key":"2580_CR41","unstructured":"R. de Wolf: Quantum computing and communication complexity, PhD thesis, University of Amsterdam, 2001."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2580-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-011-2580-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2580-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,17]],"date-time":"2021-12-17T18:36:40Z","timestamp":1639766200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-011-2580-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["2580"],"URL":"https:\/\/doi.org\/10.1007\/s00493-011-2580-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}