RECORD
Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
Data Structures and Algorithms · Submitted 13 Feb 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We prove that this problem can be solved deterministically in polynomial time when $m\geq 49 d^2$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Given $v_1,\ldots, v_m\in\mathbb{C}^d$ with $\|v_i\|^2= \alpha$ for all $i\in[m]$ as input and suppose $\sum_{i=1}^m | \langle u, v_i \rangle |^2 = 1$ for every unit vector $u\in\mathbb{C}^d$, Weaver's discrepancy problem asks for a partition $S_1, S_2$ of $[m]$, such that $\sum_{i\in S_{j}} |\langle u, v_i \rangle|^2 \leq 1 -\theta$ for some universal constant $\theta$, every unit vector $u\in\mathbb{C}^d$ and every $j\in\{1,2\}$. We prove that this problem can be solved deterministically in polynomial time when $m\geq 49 d^2$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Given $v_1,\ldots, v_m\in\mathbb{C}^d$ with $\|v_i\|^2= \alpha$ for all $i\in[m]$ as input and suppose $\sum_{i=1}^m | \langle u, v_i \rangle |^2 = 1$ for every unit vector $u\in\mathbb{C}^d$, Weaver's discrepancy problem asks for a partition $S_1, S_2$ of $[m]$, such that $\sum_{i\in S_{j}} |\langle u, v_i \rangle|^2 \leq 1 -\theta$ for some universal constant $\theta$, every unit vector $u\in\mathbb{C}^d$ and every $j\in\{1,2\}$. | background 1.00 | 0.07 | 0.04 | asserted 0.85 |
| s1 | We prove that this problem can be solved deterministically in polynomial time when $m\geq 49 d^2$. | result 0.74 | 0.96 | 0.96 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Given $v_1,\ldots, v_m\in\mathbb{C}^d$ with $\|v_i\|^2= \alpha$ for all $i\in[m]$ as input and suppose $\sum_{i=1}^m | \langle u, v_i \rangle |^2 = 1$ for every unit vector $u\in\mathbb{C}^d$, Weaver's discrepancy problem asks for a partition $S_1, S_2$ of $[m]$, such that $\sum_{i\in S_{j}} |\langle u, v_i \rangle|^2 \leq 1 -\theta$ for some universal constant $\theta$, every unit vector $u\in\mathbb{C}^d$ and every $j\in\{1,2\}$. We prove that this problem can be solved deterministically in polynomial time when $m\geq 49 d^2$.
Human review
References
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites
Compares with 1 paper
-
Weaver [ref] gives a polynomial-time algorithm for a one-sided version of the $𝖪𝖲_2$ problem based on the BSS framework for spectral sparsification [ref] .
The Kadison-Singer problem in discrepancy theory, II · Related Work · 0.93
Cites as background 1 paper
-
Our approach further relates to the determinant maximisation problem which has been extensively studied in the field of experimental design [ref] .
Maximizing the Minimum Eigenvalue in Constant Dimension · Related Work · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.