Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank

DOI10.1145/3564246.3585103MaRDI QIDQ6408645zbMATH OpenFDO

Authors N. Bansal, Haotian Jiang, Raghu Meka

Publication date 23 August 2022

Full work available at URL https://doi.org/10.1145/3564246.3585103

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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.

Cited in

(6)

• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• Revisit the partial coloring method: prefix spencer and sampling
• Better sparsifiers for directed Eulerian graphs
• Average-case matrix discrepancy: satisfiability bounds
• Zero-one laws for random feasibility problems
• Weaver's discrepancy for Gaussian random vectors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408645)