The log-rank conjecture and low degree polynomials
We formulate several questions concerning the intersections of sets of Boolean roots of low degree polynomials. Two of these questions we show to be equivalent to the Log-Rank Conjecture from communication complexity. We further exhibit a slightly stronger formulation which we prove to be false, and a weaker formulation which we prove to be true. These results suggest a possible new approach to the Log-Rank Conjecture. (C) 2003 Elsevier B.V. All rights reserved.
log-rank conjecture communication complexity boolean polynomials computational complexity