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.
翻译:对于涉及随机性的许多计算问题, 解决方案空间的复杂几何特征被用来严格排除强大的算法类别。 这通常通过多重叠差距属性的透镜来实现 。 多重叠差距属性( m$- OGP ) 是一个对显示输入稳定性的算法的严格屏障。 在本文中, 我们侧重于两种模型的算法可感性:(一) 差异最小化, (二) 对称二进制概念(\ textt{SBP} ), 随机限制满意度问题, 以及单层神经网络的玩具模型。 我们的第一个焦点是在线算法的限度。 通过建立和利用新的几何几何障碍, 我们获得了对在线算法的精确保证。 我们的结果匹配了已知的最佳算法保证, 直至以随机的基数( $malcalcal cal) 来找到一个恒定差异的解决方案。 以随机基数 美元为基数的基数 美元 ; 美元 基数 基数 基数 的数值 和 基数的计算结果 。