×

On rank vs. communication complexity. (English) Zbl 0845.68038

Summary: This paper concerns the open problem of Lovász and Saks regarding the relationship between the communication complexity of a Boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68R05 Combinatorics in computer science
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Software:

GRAFFITI
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, P. Seymour: A counterexample to the rank-covering conjectureJ. Graph Theory,13, (1989), 523-525. · Zbl 0674.05029 · doi:10.1002/jgt.3190130413
[2] S. Fajtlowicz: On conjectures of Graffiti II,Congresus Numeratum 60 (1987), 189-198. · Zbl 0713.05054
[3] B. Kalyanasundaram andG. Schnitger: The probabilistic communication complexity of set intersection,2nd Structure in Complexity Theory Conference, (1987), 41-49.
[4] E. Kushilevitz: private communication, 1994.
[5] L. Lov?sz: Communication Complexity: A survey, in:Paths, Flows, and VLSI Layout, B. H. Korte, ed., Springer Verlag, Berlin 1990.
[6] L. Lov?sz andM. Saks: Lattices, M?bius functions, and communication complexity,Proc. of the 29th FOCS, (1988), 81-90.
[7] L. Lov?sz andM. Saks: Private communication.
[8] K. Mehlhorn, E. M. Schmidt: Las Vegas is better than determinism in VLSI and distributive computing,Proceedings of 14th STOC, (1982), 330-337.
[9] N. Nisan andM. Szegedy: On the degree of boolean functions as real polynomials,Proceedings of 24th STOC, (1992), 462-467.
[10] N. Nisan andA. Wigderson: On rank vs. communication complexity,Proceedings of 35th FOCS, (1994), 831-836.
[11] C. van Nuffelen: A bound for the chromatic number of graph,American Mathematical Monthly 83, (1976), 265-266. · Zbl 0322.05112 · doi:10.2307/2318218
[12] A. Razborov: On the distributional complexity of disjointness,Theoretical Computer Science 106 (1992), 385-390. · Zbl 0787.68055 · doi:10.1016/0304-3975(92)90260-M
[13] 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. · Zbl 0776.05073 · doi:10.1016/0012-365X(92)90691-8
[14] 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.
[15] A. C.-C. Yao: Some complexity questions related to distributive computing.Proceedings of 11th STOC, (1979), 209-213.
[16] A. C.-C. Yao: Lower Bounds by Probabilistic Arguments,Proc. 24th FOCS, (1983), 420-428.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.