Sudakov Benny, Tomon István
ETH Zurich, Zürich, Switzerland.
Umeå University, Umeå, Sweden.
Math Program. 2025;212(1-2):567-579. doi: 10.1007/s10107-024-02117-9. Epub 2024 Jul 5.
Given an binary matrix with (where || denotes the number of 1 entries), define the of as . Using semidefinite programming and spectral techniques, we prove that if and , then We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any binary matrix of rank at most contains an sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank is at most .
给定一个具有(m)行(n)列的二进制矩阵(A)（其中(\vert\vert A\vert\vert)表示(A)中(1)元素的个数），定义(A)的(r)-范数为(\vert\vert A\vert\vert_r = \left(\sum_{i=1}^m\sum_{j=1}^n a_{ij}^r\right)^{\frac{1}{r}})。利用半定规划和谱技术，我们证明如果(r \geq 2)且(m,n \geq 1)，那么(\vert\vert A\vert\vert_r \leq \sqrt{mn}\left(\frac{\vert\vert A\vert\vert}{\sqrt{mn}}\right)^{\frac{2}{r}})。我们利用这个结果对洛夫特关于对数秩猜想的最著名上界进行了适度改进。我们证明任何秩至多为(r)的(m\times n)二进制矩阵(A)都包含一个大小为(\left(\frac{m}{r}\right)^{\frac{r}{2}}\times\left(\frac{n}{r}\right)^{\frac{r}{2}})的全(1)或全(0)子矩阵，这意味着任何秩为(r)的布尔函数的确定性通信复杂度至多为(r\log\min{m,n})。
