On the `log rank' - conjecture in communication complexity

Ran Raz, Boris Spieker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages168-176
Number of pages9
ISBN (Print)0818643706
StatePublished - Dec 1 1993
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Publication series

NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On the `log rank' - conjecture in communication complexity'. Together they form a unique fingerprint.

Cite this