Average-case matrix discrepancy: satisfiability bounds

Antoine Maillard

Given a sequence of $d\times d$ symmetric matrices $\{{\mathbf{W}}_i{\}}_{i=1}^n$, and a margin $\Delta >0$, we investigate whether it is possible to find signs $(ε_1, \dots, ε_n) \in \{\p…