Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

DOI10.1145/3564246.3585103arXiv2208.11286MaRDI QIDQ6408645

Raghu Meka, Haotian Jiang, Nikhil Bansal

Publication date: 23 August 2022

Abstract: We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric $dimesd$ matrices $A_1,ldots,A_n$ each with $|A_i{|}_{mathsfop}leq1$ and rank at most $n/lo{g}^{3}n$, one can efficiently find $pm1$ signs $x_1,ldots,x_n$ such that their signed sum has spectral norm $|su{m}_{i=1}^n{x}_i{A}_i{|}_{mathsfop}=O(sqrtn)$. This result also implies a $logn-Omega(loglogn)$ qubit lower bound for quantum random access codes encoding $n$ classical bits with advantage $gg1/sqrtn$. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024

This page was built for publication: Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank