JISE

The log-rank conjecture states that the deterministic communication complexity of a Boolean function g (denoted by D^cc(g)) is polynomially related to the logarithm of the rank of the communication matrix M_g where M_g is the communication matrix defined by M_g(x, y)=g(x, y). An XOR function G:{0, 1}ⁿx{0, 1}ⁿ→{0, 1} with respect to g:{0, 1}ⁿ→{0, 1} is a function defined by G(x, y)= g(x+y). It is well-known that ||ĝ||₀ = rank(M_G) where ||ĝ||₀ is the Fourier 0-norm of g, M_G is the communication matrix defined by M_G(x, y)=G(x, y), and rank(M_G) is the dimension of the row space of M_G over reals. The log-rank conjecture for XOR functions is equivalent to the question whether the deterministic communication complexity of an XOR function G with respect to a function G is polynomially related to the logarithm of the Fourier sparsity of g, namely D^cc(G)=log^c (||ĝ||₀) for a fixed constant c. Previously, the log-rank conjecture holds for XOR functions with respect to symmetric functions, linear threshold functions, monotone functions, AC⁰ functions, and constant-degree polynomials over F₂.
In this paper, we consider a special class of functions called read-k polynomials over F₂. We study the communication complexity of the XOR function G with respect to a read-k polynomial g. We show that D^cc(G)=O(kd²log(||ĝ||₁)) where d is the F₂-degree of g. By the well-known bound that d <= log(||ĝ||₀), we conclude that D^cc(G) = O(klog³(||ĝ|||₀)). In particular, if k=log^O(1)(||ĝ|||₀), then we have D^cc(G)=O(log^O(1)(rank(M_G))).