@inproceedings{2177695c0ace440aae077591cabfaf90,
title = "On the `log rank' - conjecture in communication complexity",
abstract = "We show the existence of a non-constant gap between the communication complexity of a function and the logarithm of the rank of its input matrix. We consider the following problem: each of two players gets a perfect matching between two n-element sets of vertices. Their goal is to decide whether or not the union of the two matchings forms a Hamiltonian cycle. We prove: 1) The rank of the input matrix over the reals for this problem is 2O(n). 2) The non-deterministic communication complexity of the problem is Ω(n log log n). Our result also supplies a superpolynomial gap between the chromatic number of a graph and the rank of its adjacency matrix. Another conclusion from the second result is an Ω(n log log n) lower bound for the graph connectivity problem in the non-deterministic case. We make use of the theory of group representations for the first result. The second result is proved by an information theoretic argument.",
author = "Ran Raz and Boris Spieker",
year = "1993",
language = "English (US)",
isbn = "0818643706",
series = "Annual Symposium on Foundatons of Computer Science (Proceedings)",
publisher = "Publ by IEEE",
pages = "168--176",
editor = "Anon",
booktitle = "Annual Symposium on Foundatons of Computer Science (Proceedings)",
note = "Proceedings of the 34th Annual Symposium on Foundations of Computer Science ; Conference date: 03-11-1993 Through 05-11-1993",
}