2026-08-17T08:57:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17162 2024-03-06T10:59:08Z ddc:004 open_access

Hardness Results for Weaver’s Discrepancy Problem Spielman, Daniel A. Zhang, Peng Discrepancy Problem Kadison-Singer Problem Hardness of Approximation Marcus, Spielman and Srivastava (Annals of Mathematics 2014) solved the Kadison-Singer Problem by proving a strong form of Weaver’s conjecture: they showed that for all α > 0 and all lists of vectors of norm at most √α whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most √{8α} + 2α. We prove that it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least η √α, for some absolute constant η > 0. Thus, it is NP-hard to construct a signing that is a constant factor better than that guaranteed to exist. For α = 1/4, we prove that it is NP-hard to distinguish whether there is a signed sum that equals the zero matrix from the case in which every signed sum has operator norm at least 1/4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel A. Spielman and Peng Zhang 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.40 urn:nbn:de:0030-drops-171628 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode