The Log-Rank Conjecture and low degree polynomials |
| |
Authors: | Paul Valiant |
| |
Affiliation: | Stanford University, P.O. Box 17308, Stanford, CA 94309, USA |
| |
Abstract: | 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. |
| |
Keywords: | Log-Rank Conjecture Communication complexity Boolean polynomials Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |