The Log-Rank Conjecture for Read-k XOR Functions

摘要

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}(n)x{0, 1}(n)-{0, 1} with respect to g:{0, 1}(n)-{0, 1} is a function defined by G(x, y) = g(x circle plus y). It is well-known that parallel to(g) over cap parallel to(0) = rank(M-G) where parallel to(g) over cap parallel to(0) 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) (parallel to(g) over cap parallel to(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, AC(0) functions, and constant-degree polynomials over F-2.