{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:27:32Z","timestamp":1771468052142,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"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":[[1995,12]]},"DOI":"10.1007\/bf01192527","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:09:11Z","timestamp":1108728551000},"page":"557-565","source":"Crossref","is-referenced-by-count":87,"title":["On rank vs. communication complexity"],"prefix":"10.1007","volume":"15","author":[{"given":"Noam","family":"Nisan","sequence":"first","affiliation":[]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1002\/jgt.3190130413","volume":"13","author":"N. Alon","year":"1989","unstructured":"N. Alon, P. Seymour: A counterexample to the rank-covering conjectureJ. Graph Theory,13, (1989), 523?525.","journal-title":"J. Graph Theory"},{"key":"CR2","first-page":"189","volume":"60","author":"S. Fajtlowicz","year":"1987","unstructured":"S. Fajtlowicz: On conjectures of Graffiti II,Congresus Numeratum 60 (1987), 189?198.","journal-title":"Congresus Numeratum"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram andG. Schnitger: The probabilistic communication complexity of set intersection,2nd Structure in Complexity Theory Conference, (1987), 41?49.","DOI":"10.1109\/PSCT.1987.10319253"},{"key":"CR4","unstructured":"E. Kushilevitz: private communication, 1994."},{"key":"CR5","volume-title":"Paths, Flows, and VLSI Layout","author":"L. Lov\ufffdsz","year":"1990","unstructured":"L. Lov\ufffdsz: Communication Complexity: A survey, in:Paths, Flows, and VLSI Layout, B. H. Korte, ed., Springer Verlag, Berlin 1990."},{"key":"CR6","unstructured":"L. Lov\ufffdsz andM. Saks: Lattices, M\ufffdbius functions, and communication complexity,Proc. of the 29th FOCS, (1988), 81?90."},{"key":"CR7","unstructured":"L. Lov\ufffdsz andM. Saks: Private communication."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, E. M. Schmidt: Las Vegas is better than determinism in VLSI and distributive computing,Proceedings of 14th STOC, (1982), 330?337.","DOI":"10.1145\/800070.802208"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"N. Nisan andM. Szegedy: On the degree of boolean functions as real polynomials,Proceedings of 24th STOC, (1992), 462?467.","DOI":"10.1145\/129712.129757"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"N. Nisan andA. Wigderson: On rank vs. communication complexity,Proceedings of 35th FOCS, (1994), 831?836.","DOI":"10.1109\/SFCS.1994.365711"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1080\/00029890.1976.11994095","volume":"83","author":"C. Nuffelen van","year":"1976","unstructured":"C. van Nuffelen: A bound for the chromatic number of graph,American Mathematical Monthly 83, (1976), 265?266.","journal-title":"American Mathematical Monthly"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A. Razborov","year":"1992","unstructured":"A. Razborov: On the distributional complexity of disjointness,Theoretical Computer Science 106 (1992), 385?390.","journal-title":"Theoretical Computer Science"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0012-365X(92)90691-8","volume":"108","author":"A. Razborov","year":"1992","unstructured":"A. Razborov, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear,Discrete Math.,108, (1992), 393?396.","journal-title":"Discrete Math."},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"R. Raz andB. Spiker: On the Log-Rank conjecture in communication complexity,Proc. of the 34th FOCS, (1993), 168?176;Combinatorica 15(4), (1995), 567?588.","DOI":"10.1007\/BF01192528"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao: Some complexity questions related to distributive computing.Proceedings of 11th STOC, (1979), 209?213.","DOI":"10.1145\/800135.804414"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"A. C.-C. Yao: Lower Bounds by Probabilistic Arguments,Proc. 24th FOCS, (1983), 420?428.","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192527.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01192527\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01192527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:19:33Z","timestamp":1734956373000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01192527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF01192527"],"URL":"https:\/\/doi.org\/10.1007\/bf01192527","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}