Derandomizing Matrix Concentration Inequalities from Free Probability
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918475095605248 |
|---|---|
| author | Wang, Robert Lau, Lap Chi Zhou, Hong |
| author_facet | Wang, Robert Lau, Lap Chi Zhou, Hong |
| contents | Recently, sharp matrix concentration inequalities~\cite{BBvH23,BvH24} were developed using the theory of free probability. In this work, we design polynomial time deterministic algorithms to construct outcomes that satisfy the guarantees of these inequalities. As direct consequences, we obtain polynomial time deterministic algorithms for the matrix Spencer problem~\cite{BJM23} and for constructing near-Ramanujan graphs. Our proofs show that the concepts and techniques in free probability are useful not only for mathematical analyses but also for efficient computations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_08111 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Derandomizing Matrix Concentration Inequalities from Free Probability Wang, Robert Lau, Lap Chi Zhou, Hong Data Structures and Algorithms Discrete Mathematics Combinatorics Probability 60B20, 05C80, 46L54, 15B52 Recently, sharp matrix concentration inequalities~\cite{BBvH23,BvH24} were developed using the theory of free probability. In this work, we design polynomial time deterministic algorithms to construct outcomes that satisfy the guarantees of these inequalities. As direct consequences, we obtain polynomial time deterministic algorithms for the matrix Spencer problem~\cite{BJM23} and for constructing near-Ramanujan graphs. Our proofs show that the concepts and techniques in free probability are useful not only for mathematical analyses but also for efficient computations. |
| title | Derandomizing Matrix Concentration Inequalities from Free Probability |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Probability 60B20, 05C80, 46L54, 15B52 |
| url | https://arxiv.org/abs/2601.08111 |