patternMinor
Worst known case for log rank conjecture
Viewed 0 times
caseranklogconjectureforknownworst
Problem
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.
$$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.
Solution
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.
$$
$$
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.
$$
Context
StackExchange Computer Science Q#69892, answer score: 4
Revisions (0)
No revisions yet.