Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910329074614272 |
|---|---|
| author | Jourdan, Ben Macgregor, Peter Sun, He |
| author_facet | Jourdan, Ben Macgregor, Peter Sun, He |
| contents | Given $v_1,\ldots, v_m\in\mathbb{C}^d$ with $\|v_i\|^2= α$ 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 -θ$ for some universal constant $θ$, 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08545 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime Jourdan, Ben Macgregor, Peter Sun, He Data Structures and Algorithms Given $v_1,\ldots, v_m\in\mathbb{C}^d$ with $\|v_i\|^2= α$ 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 -θ$ for some universal constant $θ$, 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$. |
| title | Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.08545 |