{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:03Z","timestamp":1781078403258,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf01206317","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T14:33:05Z","timestamp":1109255585000},"page":"191-204","source":"Crossref","is-referenced-by-count":64,"title":["Super-logarithmic depth lower bounds via the direct sum in communication complexity"],"prefix":"10.1007","volume":"5","author":[{"given":"Mauricio","family":"Karchmer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","first-page":"1","volume":"42","author":"A. E. Andreev","year":"1987","unstructured":"A. E. Andreev, On a Method for Obtaining more than Quadratic Effective Lower Bounds for the Complexity of ?-Schemes.Moscow University Math. Bull. 42:1 (1987).","journal-title":"Moscow University Math. Bull."},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"A. V. Aho, J. D. Ullman, and M. Yannakakis, On Notions of Information Transfer in VLSI Circuits. InProc. Fifteenth Ann. ACM Symp. Theor. Comput., 1983, 133?139.","DOI":"10.1145\/800061.808742"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, On the Extended Direct Sum Conjecture. InProc. Twenty-first Ann. ACM Symp. Theor. Comput., 1989, 177?185.","DOI":"10.1145\/73007.73024"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"J. Edmonds, R. Impagliazzo, S. Rudich, and J. Sgall, Communication Complexity towards Lower Bounds on Circuit Depth. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 249?257.","DOI":"10.1109\/SFCS.1991.185375"},{"key":"CR5","unstructured":"T. Feder,Personal communication, 1990."},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"T. Feder, E. Kushilevitz, and M. Naor, Amortized Communication Complexity. InProc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 239?248.","DOI":"10.1109\/SFCS.1991.185374"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(81)90074-8","volume":"16","author":"G. Galibati","year":"1981","unstructured":"G. Galibati andM. J. Fischer, On the Complexity of 2-Output Boolean Networks.Theoret. Comput. Sci. 16 (1981), 177?185.","journal-title":"Theoret. Comput. Sci."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"J. Hastad, The Shrinkage Constant is 2. InProc. 34th Ann. IEEE Symp. Found. Comput. Sci., 1993, 114?123.","DOI":"10.1109\/SFCS.1993.366876"},{"key":"CR9","unstructured":"J. Hastad and A. Wigderson, Composition of the Universal Relation. InAmer. Math. Soc.?DIMACS series, ed.J. Y. Cai, to appear."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"V. Khrapchenko, A Method of Determining Lower Bounds for the Complexity of ?-Schemes.Math. Notes Acad. Sci. USSR (1971), 474?479.","DOI":"10.1007\/BF01747074"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01113923","volume":"124","author":"W. M. Kantor","year":"1972","unstructured":"W. M. Kantor, On Incidence Matrices of Finite Projective and Affine Spaces.Math. Z. 124 (1972), 315?318.","journal-title":"Math. Z."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Karchmer,Communication Complexity: A new Approach to Circuit Depth. MIT Press, 1989.","DOI":"10.7551\/mitpress\/1948.001.0001"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. Karchmer, E. Kushilevitz, and N. Nisan, Fractional Covers and Communication Complexity. InProc. 7th Ann. IEEE Conf. Structure in Complexity Theory, 1992, 262?274.","DOI":"10.1109\/SCT.1992.215401"},{"key":"CR14","unstructured":"M. Karchmer, R. Raz, and A. Wigderson, On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity. InProc. 6th Ann. IEEE Conf. Structure in Complexity Theory, 1991."},{"issue":"2","key":"CR15","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer andA. Wigderson, Monotone Circuits for Connectivity Require Super-Logarithmic Depth.SIAM J. Disc. Math. 3:2 (1990), 255?265.","journal-title":"SIAM J. Disc. Math."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and E. M. Schmidt, Las Vegas is Better than Determinism in VLSI and Distributive Computing. InProc. Fourteenth Ann. ACM Symp. Theor. Comput., 1982, 330?337.","DOI":"10.1145\/800070.802208"},{"key":"CR17","unstructured":"P. Pudl\u00e1k,Personal communication, 1992."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Probabilistic Communication Complexity of Boolean Relations. InProc. 30th Ann. IEEE Symp. Found. Comput. Sci., 1989, 562?567.","DOI":"10.1109\/SFCS.1989.63535"},{"issue":"1","key":"CR19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"A. A. Razborov","year":"1990","unstructured":"A. A. Razborov, Applications of Matrix Methods for the Theory of Lower Bounds in Computational Complexity.Combinatorica 10:1 (1990), 81?93.","journal-title":"Combinatorica"},{"key":"CR20","unstructured":"M. Sipser,Personal communication, 1988."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Expressing Combinatorial Optimization Problems by Linear Programs. InProc. Twentieth ACM Symp. Theor. Comput., 1988, 223?228.","DOI":"10.1145\/62212.62232"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"A. C. C. Yao, Some Complexity Questions Related to Distributive Computing. InProc. Eleventh Ann. ACM Symp. Theor. Comput., 1979, 209?213.","DOI":"10.1145\/800135.804414"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206317.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206317\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:40:49Z","timestamp":1734979249000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":22,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF01206317"],"URL":"https:\/\/doi.org\/10.1007\/bf01206317","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}