[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]

Journal of Information Science and Engineering, Vol. 34 No. 2, pp. 391-399

The Log-Rank Conjecture for Read-k XOR Functions

Department of Computer Science and Information Engineering
National Taipei University
New Taipei City, 237 Taiwan
E-mail: {jcchang; hsinlung}@mail.ntpu.edu.tw

The log-rank conjecture states that the deterministic communication complexity of a Boolean function g (denoted by Dcc(g)) is polynomially related to the logarithm of the rank of the communication matrix Mg where Mg is the communication matrix defined by Mg(x, y)=g(x, y). An XOR function G:{0, 1}nx{0, 1}n→{0, 1} with respect to g:{0, 1}n→{0, 1} is a function defined by G(x, y)= g(x+y). It is well-known that ||ĝ||0 = rank(MG) where ||ĝ||0 is the Fourier 0-norm of g, MG is the communication matrix defined by MG(x, y)=G(x, y), and rank(MG) is the dimension of the row space of MG 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 Dcc(G)=logc (||ĝ||0) for a fixed constant c. Previously, the log-rank conjecture holds for XOR functions with respect to symmetric functions, linear threshold functions, monotone functions, AC0 functions, and constant-degree polynomials over F2.
In this paper, we consider a special class of functions called read-k polynomials over F2. We study the communication complexity of the XOR function G with respect to a read-k polynomial g. We show that Dcc(G)=O(kd2log(||ĝ||1)) where d is the F2-degree of g. By the well-known bound that d <= log(||ĝ||0), we conclude that Dcc(G) = O(klog3(||ĝ|||0)). In particular, if k=logO(1)(||ĝ|||0), then we have Dcc(G)=O(logO(1)(rank(MG))).

Keywords: communication complexity, the log-rank conjecture, read-k polynomials, read-k XOR functions, fourier sparsity

  Retrieve PDF document (JISE_201802_05.pdf)