Metraipolis › archive › dc_e62da28d698b
A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture — arXiv:2609.18913
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.18913
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T17:09:22.527Z
- SHA-256 of the archived text
782334513ee3e295b8f0eb49d8cef1310e56eec186df7ff7c762ee7d6a414a7e- Stable URL of this page
https://metraipolis.com/documento/dc_e62da28d698b
How to cite
A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture — arXiv:2609.18913 — arXiv (en), https://arxiv.org/abs/2609.18913 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e62da28d698b (Metraipolis archive dc_e62da28d698b, sha256 782334513ee3e295b8f0eb49d8cef1310e56eec186df7ff7c762ee7d6a414a7e)
BibTeX
@misc{dce62da28d698b,
title = {A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture — arXiv:2609.18913},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.18913},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e62da28d698b; sha256 782334513ee3e295b8f0eb49d8cef1310e56eec186df7ff7c762ee7d6a414a7e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18913. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqrt\varepsilon$. The algorithm walks from the origin of the hypercube to a vertex, fixing coordinates as they hit a face. Its potential measures a soft spectral edge of the discrepancy matrix perturbed by an operator-valued free semicircular element. The perturbation's covariance vanishes as the coefficients reach their endpoints. Inspired by the free interpolation approach of Bandeira, Boedihardjo, and van Handel \cite{bbvh2023}, we combine Lehner's variational formula \cite{lehner1999} with spectral Tsallis--$1/2$ regularization used in \cite{allenZhuLiaoOrecchia2015} and \cite{pesentivladu2026}. The resulting potential has a finite-dimensional SDP formulation, allowing the discrepancy and remaining covariance to be analyzed together. We analyze the optimizer's stability through the linearized Karush--Kuhn--Tucker (KKT) system of a regularized min--max problem, whose stationarity equations are related to the matrix Dyson equation \cite{erdos2019}. This gives the movement rule: either a coordinate can move toward its nearer endpoint at small spectral cost, or a low-curvature direction orthogonal to the current coefficient vector allows further progress. Choosing the better sign of this direction controls discrepancy while increasing the squared distance from the origin. Upcoming work \cite{kathuria2026higherRank} will address higher-rank Kadison-Singer and spectrally thin trees. Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Functional Analysis (math.FA).
Pagina del lavoro: https://arxiv.org/abs/2609.18913 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:15.269Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).