2022/08/24 by Nikhil Bansal, Bansal, Nikhil, Haotian Jiang +3 · 2 citations
Engineering · Mathematics · #Advanced Algebra and Geometry #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Random Matrices and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2208.11286
openalex publication_date 2022/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d × d matrices A1,…,An each with ‖Ai‖op ≤ 1 and rank at most n/log3 n, one can efficiently find ± 1 signs x1,…,xn such that their signed sum has spectral norm ‖∑i=1n xi Ai‖op = O(√(n)). This result also implies a log n - Ω( log log n) qubit lower bound for quantum random access codes encoding n classical bits with advantage ≫ 1/√(n). 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.