  For many computational problems involving randomness, intricate geometric
features of the solution space have been used to rigorously rule out powerful
classes of algorithms. This is often accomplished through the lens of the multi
Overlap Gap Property ($m$-OGP), a rigorous barrier against algorithms
exhibiting input stability. In this paper, we focus on the algorithmic
tractability of two models: (i) discrepancy minimization, and (ii) the
symmetric binary perceptron (\texttt{SBP}), a random constraint satisfaction
problem as well as a toy model of a single-layer neural network.
  Our first focus is on the limits of online algorithms. By establishing and
leveraging a novel geometrical barrier, we obtain sharp hardness guarantees
against online algorithms for both the \texttt{SBP} and discrepancy
minimization. Our results match the best known algorithmic guarantees, up to
constant factors. Our second focus is on efficiently finding a constant
discrepancy solution, given a random matrix $\mathcal{M}\in\mathbb{R}^{M\times
n}$. In a smooth setting, where the entries of $\mathcal{M}$ are i.i.d.
standard normal, we establish the presence of $m$-OGP for $n=\Theta(M\log M)$.
Consequently, we rule out the class of stable algorithms at this value. These
results give the first rigorous evidence towards a conjecture of Altschuler and
Niles-Weed~\cite[Conjecture~1]{altschuler2021discrepancy}.
  Our methods use the intricate geometry of the solution space to prove tight
hardness results for online algorithms. The barrier we establish is a novel
variant of the $m$-OGP. Furthermore, it regards $m$-tuples of solutions with
respect to correlated instances, with growing values of $m$, $m=\omega(1)$.
Importantly, our results rule out online algorithms succeeding even with an
exponentially small probability.
