{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:24Z","timestamp":1742600424389,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_50","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:31Z","timestamp":1330290271000},"page":"617-630","source":"Crossref","is-referenced-by-count":1,"title":["The \u201clog rank\u201d conjecture for modular communication complexity"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Meinel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"Waack","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"50_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov, R. Smolensky, On Lower Bounds for Read-k-Times Branching Programs, Computational Complexity 3(1993), pp. 1\u201318.","journal-title":"Computational Complexity"},{"key":"50_CR2","doi-asserted-by":"crossref","unstructured":"C. Damm, M. Krause, Ch. Meinel, St. Waack, Separating Counting Communication Complexity Classes, in: Proc. 9th STACS, Lecture Notes in Computer Science 577, Springer Verlag 1992, pp. 281\u2013293.","DOI":"10.1007\/3-540-55210-3_190"},{"key":"50_CR3","doi-asserted-by":"crossref","unstructured":"A. Hajnal, W. Maass, G. Turan, On the Communication Complexity of Graph Problems, in: Proc. 20th ACM STOC 1988, pp. 186\u2013191.","DOI":"10.1145\/62212.62228"},{"key":"50_CR4","doi-asserted-by":"crossref","unstructured":"M. Krause, St. Waack, Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fanin, in: Proc. 32nd IEEE FOCS 1991, pp. 777\u2013782.","DOI":"10.1109\/SFCS.1991.185448"},{"key":"50_CR5","doi-asserted-by":"crossref","unstructured":"S. Lokam, Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity, in: Proc. 36th IEEE FOCS 1995.","DOI":"10.1109\/SFCS.1995.492457"},{"key":"50_CR6","unstructured":"L. Lovasz, Communication complexity: A survey, in: Paths, Flows and VLSI-Layouts, Springer-Verlag 1990, pp. 235\u2013266."},{"key":"50_CR7","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1016\/0022-0000(93)90035-U","volume":"47","author":"L. Lovasz","year":"1993","unstructured":"L. Lovasz, M. Saks, Communication Complexity and Combinatorial Lattice Theory, Journal of Computer and System Sciences 47(1993), pp. 322\u2013349.","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR8","unstructured":"Ch. Meinel, St. Waack, The M\u201d obius Function, Variation Ranks, and \u0398(n) \u2014 Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem, ECCC-Report TR94-022."},{"key":"50_CR9","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, E. M. Schmidt, Las Vegas is Better than Determinism in VLSI and Distributed Computing, in: Proc. 14th ACM STOC 1982, pp. 330\u2013337.","DOI":"10.1145\/800070.802208"},{"issue":"2","key":"50_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01215351","volume":"14","author":"P. Pudlak","year":"1994","unstructured":"P. Pudlak, Large Communication in Constant Depth Circuits, Combinatorica 14(2)(1994), pp. 203\u2013216.","journal-title":"Combinatorica"},{"key":"50_CR11","first-page":"598","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"A.A. Razborov, Lower bounds for the size of circuits of bounded depth with basis {\u2227, \u2295}, Journ. Math. Zametki 41(1987), pp. 598\u2013607.","journal-title":"Journ. Math. Zametki"},{"key":"50_CR12","unstructured":"A.A. Razborov, On Rigid Matrices, Manuscript."},{"key":"50_CR13","doi-asserted-by":"crossref","unstructured":"R. Raz, B. Spieker, On the \u201clog rank\u201d\u2014 Conjecture in Communication Complexity, in: Proc. 34th IEEE FOCS 1993, pp. 168\u2013176.","DOI":"10.1109\/SFCS.1993.366870"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"L. Skyum, L. V. Valiant, A Complexity Theory Based on Boolean Algebra, in: Proc. 22th IEEE FOCS, pp. 244\u2013253.","DOI":"10.1109\/SFCS.1981.3"},{"key":"50_CR15","doi-asserted-by":"crossref","unstructured":"V. Shoup, R. Smolensky, Lower Bounds for Polynomial Evaluation and Interpolation, in: Proc. 32nd IEEE FOCS (1991), pp. 378\u2013383.","DOI":"10.1109\/SFCS.1991.185394"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity, in: Proc. 19th ACM STOC (1987), pp. 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"50_CR17","unstructured":"A. Wigderson, The Complexity of Graph Connectivity, TR 92-19, Leibnitz Center for Research in Computer Science, Institute of Computer Science, Hebrew University, Jerusalem."},{"key":"50_CR18","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao, Some Complexity Questions Related to Distributed Computing, in: Proc. 11st ACM STOC 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"},{"key":"50_CR19","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao, On ACC and Threshold Circuits, in: Proc. 31st IEEE FOCS 1990, pp. 619\u2013627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:59Z","timestamp":1742598659000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}