First-moment lower-bound conjecture for average-case matrix discrepancy
First-moment lower-bound conjecture for average-case matrix discrepancy
Let be i.i.d. random symmetric matrices, where , almost surely, the distribution is “sufficiently nice,” and the effective rank is . Informal discrepancy lower bound. With high probability,
The phrases “sufficiently nice” distribution and “effective rank” are deliberately left undefined in the source, so this is an informal conjecture about first-moment lower bounds for average-case matrix discrepancy. Its status is open.
Sources & referencesView supporting material
Primary source
Dmitriy Kunisky and Peiyuan Zhang, “Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms”, arXiv:2307.10055 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.