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 matcliings 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 Ω(nloglog 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 Ω(nloglog 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.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics
- Mathematics Subject Classification (1991): 68Q15, 05C50, 68R10, 05C15