Matrix discrepancy from Quantum communication
Matrix discrepancy from Quantum communication
复制标题
量子通信的矩阵差异
DOI：
10.1145/3519935.3519954
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Shetty, Abhishek
中科院分区：
文献类型：
--
作者：
Hopkins, Samuel B.;Raghavendra, Prasad;Shetty, Abhishek
我们开发了一种新的差异最小化和（量子）通信复杂性之间的连接。作为应用，我们解决了矩阵Spencer猜想的一个实质特例.特别地，我们证明了对于每个矩阵集合A1，...，Anwith|| AI|| ≤ 1且||AI|| F≤n1/4存在符号x ∈ { ± 1} n使得∑i≤ nxiAi的最大特征值至多为O（<$n）.我们给出了一个基于部分着色和半定规划的多项式时间算法来求解这类问题，为利用通信复杂性和信息论的工具来研究差异性问题开辟了一条新的途径。我们主要结果的证明结合了重复（量子）通信协议转录本的简单压缩方案与量子态纯化、量子信息的Holevo界限以及草图和降维工具。我们的方法也提供了一个有前途的途径来解决矩阵斯宾塞猜想完全-我们表明，它是由一个自然的量子通信复杂性的猜想。
We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of theMatrix Spencerconjecture. In particular, we show that for every collection of symmetricn×nmatricesA1,…,Anwith ||Ai|| ≤ 1 and ||Ai||F≤n1/4there exist signsx∈ { ± 1}nsuch that the maximum eigenvalue of ∑i≤nxiAiis at mostO(√n). We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find suchx.Our techniques open a new avenue to use tools from communication complexity and information theory to study discrepancy. The proof of our main result combines a simple compression scheme for transcripts of repeated (quantum) communication protocols with quantum state purification, the Holevo bound from quantum information, and tools from sketching and dimensionality reduction. Our approach also offers a promising avenue to resolve the Matrix Spencer conjecture completely – we show it is implied by a natural conjecture in quantum communication complexity.
登录
查看更多内容
DOI：
10.1137/141000282
发表时间：
2014
期刊：
2014 IEEE 55th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
T. Rothvoss
通讯作者：
T. Rothvoss
对于 1 阶矩阵来说，四个偏差就足够了
DOI：
10.1016/j.aim.2020.107366
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Rasmus Kyng;K. Luh;Zhao Song
通讯作者：
Zhao Song
影响因子：
1.6
作者：
Lovett, Shachar;Meka, Raghu
通讯作者：
Meka, Raghu
线性尺寸稀疏器和算子规范球的几何形状
DOI：
10.1137/1.9781611975994.143
发表时间：
2020
期刊：
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Reis, Victor;Rothvoss, Thomas
通讯作者：
Rothvoss, Thomas
矩阵差异的新框架：通过镜像下降的部分着色边界
DOI：
10.1145/3519935.3519967
发表时间：
2021
期刊：
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
D. Dadush;Haotian Jiang;Victor Reis
通讯作者：
Victor Reis