@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",

month = dec,

day = "1",

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",

}