The log rank conjecture states that there is some universal constant $c > 0$ so that

$$CC(f) = O(\log^c \text{rk}\,(M_f))$$

where $f : X \times Y \to \{0, 1\}$ is a boolean function, $CC$ denotes the deterministic communication complexity, $M_f$ is the $|X| \times |Y|$ binary matrix associated to $f$, and $\text{rk}\,(M_f)$ is the rank of $M_f$ calculated over the reals. In the literature, it mentions that this $c$, if it exists, is at least $\log_3 6 \approx 1.631\ldots$, and attributes this to an unpublished result of Kushilevitz in 1994. Does anyone know what example Kushilevitz uses to achieve this lower bound? I think it would be interesting to see what the worst case might be and it might give insight into how to solve the problem in general.


The function is described in a footnote in Nisan and Wigderson's paper On rank vs. communication complexity. It is

$$ E(z_1 \dots z_6) = \sum_i z_i - \sum_{ij} z_{i}z_{j} + \\z_1z_3z_4 + z_1z_2z_5 + z_1z_4z_5 + z_2z_3z_4 + z_2z_3z_5 + \\ z_1z_2z_6 + z_1z_3z_6 + z_2z_4z_6 + z_3z_5z_6 + z_4z_5z_6. $$

| cite | improve this answer | |
  • $\begingroup$ I thought it was improved by Mika Goos. $\endgroup$ – 1.. Mar 22 '17 at 9:56
  • $\begingroup$ @Turbo That's perfectly possible. This answer doesn't update itself every time an improvement is discovered. You could add a new answer with the improvement. $\endgroup$ – Yuval Filmus Mar 22 '17 at 12:16
  • $\begingroup$ @Turbo It seems the answer is in the paper Deterministic Communication vs. Partition Number -- will give it a read $\endgroup$ – MCT Mar 22 '17 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.