First-moment lower-bound conjecture for average-case matrix discrepancy

Let A1,,ATRsymn×n\bm A_1,\dots,\bm A_T\in\mathbb{R}^{n\times n}_{\operatorname{sym}} be i.i.d. random symmetric matrices, where T=T(n)T=T(n), Ai1\|\bm A_i\|\leq1 almost surely, the distribution is “sufficiently nice,” and the effective rank is r=r(n)r=r(n). Informal discrepancy lower bound. With high probability,

Δ(A1,,AT)rTn4T/n2.\Delta(\bm A_1,\dots,\bm A_T)\gtrsim\sqrt{\frac{rT}{n}}\,4^{-T/n^2}.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.