{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:58Z","timestamp":1763467798779,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_15","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"171-182","source":"Crossref","is-referenced-by-count":32,"title":["Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity"],"prefix":"10.1007","author":[{"given":"J\u00fcrgen","family":"Forster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Krause","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satyanarayana V.","family":"Lokam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rustam","family":"Mubarakzjanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niels","family":"Schmitt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans Ulrich","family":"Simon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Frankl, and V. R\u00f6dl. Geometrical realization of set systems and probabilistic communication complexity. In Proceedings of the 26th Symposium on Foundations of Computer Science, pages 277\u2013280, 1985.","DOI":"10.1109\/SFCS.1985.30"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","volume":"37","author":"N. Alon","year":"1988","unstructured":"N. Alon and W. Maass. Meanders and their applications in lower bound arguments. Journal of Computer and System Sciences, 37:118\u2013129, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Rosa I. Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. In Proceedings of the 40\u2019th Annual Symposium on the Foundations of Computer Science, pages 616\u2013623, 1999.","DOI":"10.1109\/SFFCS.1999.814637"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. Limitations of learning via embeddings in euclidean half-spaces. In Proceedings of the 14th Annual Workshop on Computational Learning Theory, pages 385\u2013401. Springer Verlag, 2001.","DOI":"10.1007\/3-540-44581-1_25"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC 0 functions and spectral norms. In Proceedings of the 31st Symposium on Foundations of Computer Science, pages 632\u2013641, 1990.","DOI":"10.1109\/FSCS.1990.89585"},{"key":"15_CR6","unstructured":"Nello Christianini and John Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"J\u00fcrgen Forster. A linear bound on the unbounded error probabilistic communication complexity. In Proceedings of the 16th Annual Conference on Computational Complexity, pages 100\u2013106, 2001.","DOI":"10.1109\/CCC.2001.933877"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"J\u00fcrgen Forster, Niels Schmitt, and Hans Ulrich Simon. Estimating the optimal margins of embeddings in euclidean half spaces. In Proceedings of the 14th Annual Workshop on Computational Learning Theory, pages 402\u2013415. Springer Verlag, 2001.","DOI":"10.1007\/3-540-44581-1_26"},{"key":"15_CR9","doi-asserted-by":"publisher","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\u00e0k, M. Szegedy, and G. Tur\u00e1n. Threshold circuits of bounded depth. Journal of Computer and System Sciences, 46:129\u2013154, 1993.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"15_CR10","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1137\/0222057","volume":"22","author":"B. Halstenberg","year":"1993","unstructured":"Bernd Halstenberg and R\u00fcdiger Reischuk. Different modes of communication. SIAM Journal on Computing, 22(5):913\u2013934, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(95)00005-4","volume":"156","author":"M. Krause","year":"1996","unstructured":"Matthias Krause. Geometric arguments yield better bounds for threshold circuits and distributed computing. Theoretical Computer Science, 156:99\u2013117, 1996.","journal-title":"Theoretical Computer Science"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Matthias Krause and Pavel Pudl\u00e1k. On the computational power of depth-2 circuits with threshold and modulo gates. In Proceedings of the 25th Annual Symposium on Theory of Computing, pages 48\u201357, 1993.","DOI":"10.1145\/195058.195103"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Matthias Krause and Stephan Waack. Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in. In Proceedings of the 32nd Symposium on Foundations of Computer Science, pages 777\u2013782, 1991.","DOI":"10.1109\/SFCS.1991.185448"},{"issue":"1","key":"15_CR14","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"R. Paturi","year":"1986","unstructured":"Ramamohan Paturi and Janos Simon. Probabilistic communication complexity. Journal of Computer and System Sciences, 33(1):106\u2013123, 1986.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Martin Sauerhoff. On the size of randomized OBDDs and read-once branching programs for k-stable functions. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 488\u2013499. Springer Verlag, 1999.","DOI":"10.1007\/3-540-49116-3_46"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Ingo Wegner. Branching programs and binary decision diagrams \u2014 theory and applications. Monographs on Discrete Mathematics and Applications. SIAM, 2001.","DOI":"10.1137\/1.9780898719789"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:54:00Z","timestamp":1737093240000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}