{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:57:51Z","timestamp":1775282271440,"version":"3.50.1"},"reference-count":17,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3917,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2002,12]]},"DOI":"10.1016\/s0022-0000(02)00019-3","type":"journal-article","created":{"date-parts":[[2002,12,27]],"date-time":"2002-12-27T18:04:53Z","timestamp":1041012293000},"page":"612-625","source":"Crossref","is-referenced-by-count":84,"title":["A linear lower bound on the unbounded error probabilistic communication complexity"],"prefix":"10.1016","volume":"65","author":[{"given":"J\u00fcrgen","family":"Forster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(02)00019-3_BIB1","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Frankl, V. R\u00f6dl, Geometrical realization of set systems and probabilistic communication complexity, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Portland, OR, 1985.","DOI":"10.1109\/SFCS.1985.30"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB2","doi-asserted-by":"crossref","unstructured":"S. Ben-David, N. Eiron, H.U. Simon, Limitations of learning via embeddings in Euclidean half-spaces (David P. Helmbold and Bob Williamson, Eds.), Proceedings of the 14th Annual Workshop on Computational Learning Theory, Springer, Berlin, Heidelberg, 2001.","DOI":"10.1007\/3-540-44581-1_25"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB3","first-page":"157","article-title":"Learnability and the Vapnik\u2013Chervonenkis dimension","volume":"100","author":"Blumer","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB4","series-title":"An Introduction to Support Vector Machines","author":"Cristianini","year":"2000"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB5","unstructured":"J. Forster, A linear lower bound on the unbounded error probabilistic communication complexity (Francis M. Titsworth, Ed.), Proceedings of the 16th IEEE Annual Conference on Computational Complexity, IEEE Computer Society Press, Silver Spring, MD, 2001, pp. 100\u2013106."},{"key":"10.1016\/S0022-0000(02)00019-3_BIB6","doi-asserted-by":"crossref","unstructured":"J. Forster, M. Krause, S.V. Lokam, R. Mubarakzjanov, N. Schmitt, H.U. Simon, Relations between communication complexity, linear arrangements and computational complexity, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, Springer, Berlin, 2001, pp. 171\u2013182.","DOI":"10.1007\/3-540-45294-X_15"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB7","doi-asserted-by":"crossref","unstructured":"J. Forster, N. Schmitt, H.U. Simon, Estimating the optimal margins of embeddings in Euclidean half spaces, Proceedings of the 14th Annual Conference on Computational Learning Theory, Springer, Berlin, 2001, pp. 402\u2013415.","DOI":"10.1007\/3-540-44581-1_26"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB8","unstructured":"J. Forster, M.K. Warmuth, Relative loss bounds for temporal-difference learning, Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufmann, San Francisco, 2000, pp. 295\u2013302."},{"key":"10.1016\/S0022-0000(02)00019-3_BIB9","series-title":"Matrix Computations","author":"Golub","year":"1991"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB10","series-title":"Matrix analysis","author":"Horn","year":"1985"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB11","series-title":"An Introduction to Computational Learning Theory","author":"Kearns","year":"1994"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB12","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(95)00005-4","article-title":"Geometric arguments yield better bounds for threshold circuits and distributed computing","volume":"156","author":"Krause","year":"1996","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00019-3_BIB13","series-title":"Communication Complexity","author":"Kushilevitz","year":"1997"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB14","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","article-title":"Probabilistic communication complexity","volume":"33","author":"Paturi","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00019-3_BIB15","series-title":"Real and Complex Analysis","author":"Rudin","year":"1974"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB16","series-title":"Statistical Learning Theory","author":"Vapnik","year":"1998"},{"key":"10.1016\/S0022-0000(02)00019-3_BIB17","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory Probab. Appl."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000193?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000193?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T14:29:36Z","timestamp":1554042576000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000002000193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["S0022000002000193"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(02)00019-3","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}