首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号