The log-approximate-rank conjecture is false
The log-approximate-rank conjecture is false
复制标题
对数近似秩猜想是错误的
DOI：
10.1145/3313276.3316353
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Suhail Sherif
中科院分区：
文献类型：
--
作者：
A. Chattopadhyay;Nikhil S. Mande;Suhail Sherif
本文构造了一个2n个变量的简单全异或函数F，它的谱范数为O（n），近似秩为O（n2），近似非负秩为O（n2.5）.我们证明了它具有多项式大的随机有界错误通信复杂度Ω（n）。这产生了近似秩的对数与全函数的随机化通信复杂度之间的第一指数差距。因此，F证明了对数近似秩猜想（LARC）的反驳，LARC是由Lee和Shraibman提出的，作为确定性通信中尚未解决的对数秩猜想的随机通信的非常自然的模拟。最著名的以前的差距之间的任何总功能的两个措施是最近的4次幂分离的G 'o'os，Jayram，Pitassi和沃森。此外，我们的函数F驳斥了Grolmusz猜想和最近由Kol，Moran，Shpilka和Yehudayoff提出的对数近似非负秩猜想的变体，这两者都是LARC所暗示的。F的补有指数大的近似非负秩。这回答了Lee和Kol等人的问题，表明近似非负秩可以指数地大于近似秩。函数F也证伪了Tsang，Wong，Xie和Zhang关于布尔函数的奇偶测度的一个猜想。后一个猜想暗示了异或函数的对数秩猜想。我们很高兴地注意到，在我们发表我们的结果后不久，两个独立的研究小组，Anshu，Boddu和Touchette，以及Sinha和de Wolf，使用我们的函数F来证明量子对数秩猜想也是错误的，通过证明F具有Ω（n1/6）量子通信复杂性。
We construct a simple and total XOR function F on 2n variables that has only O(√n) spectral norm, O(n2) approximate rank and O(n2.5) approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of Ω(√n). This yields the first exponential gap between the logarithm of the approximate rank and randomized communication complexity for total functions. Thus F witnesses a refutation of the Log-Approximate-Rank Conjecture (LARC) which was posed by Lee and Shraibman as a very natural analogue for randomized communication of the still unresolved Log-Rank Conjecture for deterministic communication. The best known previous gap for any total function between the two measures is a recent 4th-power separation by G'o'os, Jayram, Pitassi and Watson. Additionally, our function F refutes Grolmusz’s Conjecture and a variant of the Log-Approximate-Nonnegative-Rank Conjecture, suggested recently by Kol, Moran, Shpilka and Yehudayoff, both of which are implied by the LARC. The complement of F has exponentially large approximate nonnegative rank. This answers a question of Lee and Kol et al., showing that approximate nonnegative rank can be exponentially larger than approximate rank. The function F also falsifies a conjecture about parity measures of Boolean functions made by Tsang, Wong, Xie and Zhang. The latter conjecture implied the Log-Rank Conjecture for XOR functions. We are pleased to note that shortly after we published our results two independent groups of researchers, Anshu, Boddu and Touchette, and Sinha and de Wolf, used our function F to prove that the Quantum-Log-Rank Conjecture is also false by showing that F has Ω(n1/6) quantum communication complexity.
DOI：
10.4230/lipics.itcs.2018.11
发表时间：
2018
期刊：
Innovations in Theoretical Computer Science Conference (ITCS 2018
影响因子：
--
作者：
Braverman, Mark;Ganor, Anat;Kol, Gillat;Raz, Ran
通讯作者：
Raz, Ran
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas
BPP 的查询到通信提升
影响因子：
1.6
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas