### 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 2^{O(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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundatons of Computer Science (Proceedings) |

Editors | Anon |

Publisher | Publ by IEEE |

Pages | 168-176 |

Number of pages | 9 |

ISBN (Print) | 0818643706 |

State | Published - Dec 1 1993 |

Event | Proceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA Duration: Nov 3 1993 → Nov 5 1993 |

### Publication series

Name | Annual Symposium on Foundatons of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | Proceedings of the 34th Annual Symposium on Foundations of Computer Science |
---|---|

City | Palo Alto, CA, USA |

Period | 11/3/93 → 11/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

*Annual Symposium on Foundatons of Computer Science (Proceedings)*(pp. 168-176). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.