论文标题
对数秩和抬起
Log-rank and lifting for AND-functions
论文作者
论文摘要
令$ f：\ {0,1 \}^n \ to \ {0，1 \} $为布尔函数，让$ f_ \ land（x，y）= f（x，x \ land y）$表示$ f $的and-function，在$ x \ x \ land y $ dem y $ dem y y y y $ debes bite and and。我们研究了$ f_ \ land $的确定性通信复杂性，并表明，最多可达$ \ log n $ factor，它在$ f_ \ land $的真实等级的对数中受多项式的界限。这是在建立对数秩的猜想和功能的$ \ log n $因素之内，而对$ f $没有假设。我们的结果与对日志秩猜想的特殊情况相反，该结果需要对$ f $（例如单调性或低$ \ $ \ mathbb {f} _2 $ degegree）进行重大限制。我们的技术也可以用来证明（在$ \ log n $ factor中）升起定理和功能，表明$ f_ \ land $的确定性通信复杂性与$ f $的否决和决策树的复杂性是多个问题相关的。 结果依赖于布尔函数的新结构结果$ f：\ {0，1 \}^n \ to \ {0，1 \} $，具有稀疏的多项式表示，这可能具有独立的利益。我们表明，如果多项式计算$ f $几乎没有单元，那么单个单元的设定系统具有小击中，其稀疏性大小poly-logarithmic。我们还建立了此结果的扩展，以更大的范围更大的范围内多线多项式$ f：\ {0,1 \}^n \ to \ mathbb {r} $。
Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_\land$. This comes within a $\log n$ factor of establishing the log-rank conjecturefor AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on $f$ such as monotonicity or low $\mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $\log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_\land$ is polynomially-related to the AND-decision tree complexity of $f$. The results rely on a new structural result regarding boolean functions $f:\{0, 1\}^n \to \{0, 1\}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:\{0,1\}^n \to \mathbb{R}$ with a larger range.
