标题： 大型平衡独立集的尖锐在线难度 显示英文标题

标题： Sharp Online Hardness for Large Balanced Independent Sets

摘要： 我们研究在密集随机二部图中寻找大$\gamma$-平衡独立集的算法问题；一个独立集是$\gamma$-平衡的，如果其顶点的$\gamma$比例位于二部划分的一侧。 在稀疏区域，Perkins 和 Wang 在低次数多项式 (LDP) 框架内建立了紧界，通过为稳定算法定制的重叠间隙属性 (OGP) 框架展示了因子$1/(1-\gamma)$的统计-计算差距。 然而，这些技术似乎无法扩展到密集设置。 对于密集随机图中的相关大独立集问题，已知最好的算法是一种本质上不稳定的在线贪心过程，而 LDP 算法在贪心算法成功的情况下也被猜想会失败。 我们证明，在密集随机二部图中，最大的$\gamma$-平衡独立集的大小为$\alpha:=\frac{\log_b n}{\gamma(1-\gamma)}$，几乎必然，其中$n$是每个二部集的大小，$p$是边概率，$b=1/(1-p)$。 我们设计了一个在线算法，对于任何$\epsilon>0$，几乎必然能实现$(1-\epsilon)(1-\gamma)\alpha$。 我们补充了一个精确的下界，表明没有在线算法可以以可忽略的概率达到$(1+\epsilon)(1-\gamma)\alpha$。 我们的结果表明，在密集情况下，同样的因子-$1/(1-\gamma)$间隙也存在，支持其猜想的普遍性。 虽然在$G(n,p)$上的经典贪心过程是直接的，但我们的算法更为复杂：它分为两个阶段，结合了停止时间和适当的截断，以确保尽管在有限信息下操作，也能满足$\gamma$-平衡性-这一全局约束。 我们的下界利用了OGP框架；我们建立在对在线模型的最近改进框架之上，并将其扩展到二部情况。 显示英文摘要

摘要： We study the algorithmic problem of finding large $\gamma$-balanced independent sets in dense random bipartite graphs; an independent set is $\gamma$-balanced if a $\gamma$ proportion of its vertices lie on one side of the bipartition. In the sparse regime, Perkins and Wang established tight bounds within the low-degree polynomial (LDP) framework, showing a factor-$1/(1-\gamma)$ statistical-computational gap via the Overlap Gap Property (OGP) framework tailored for stable algorithms. However, these techniques do not appear to extend to the dense setting. For the related large independent set problem in dense random graph, the best known algorithm is an online greedy procedure that is inherently unstable, and LDP algorithms are conjectured to fail even in the "easy" regime where greedy succeeds. We show that the largest $\gamma$-balanced independent set in dense random bipartite graphs has size $\alpha:=\frac{\log_b n}{\gamma(1-\gamma)}$ whp, where $n$ is the size of each bipartition, $p$ is the edge probability, and $b=1/(1-p)$. We design an online algorithm that achieves $(1-\epsilon)(1-\gamma)\alpha$ whp for any $\epsilon>0$. We complement this with a sharp lower bound, showing that no online algorithm can achieve $(1+\epsilon)(1-\gamma)\alpha$ with nonnegligible probability. Our results suggest that the same factor-$1/(1-\gamma)$ gap is also present in the dense setting, supporting its conjectured universality. While the classical greedy procedure on $G(n,p)$ is straightforward, our algorithm is more intricate: it proceeds in two stages, incorporating a stopping time and suitable truncation to ensure that $\gamma$-balancedness-a global constraint-is met despite operating with limited information. Our lower bound utilizes the OGP framework; we build on a recent refinement of this framework for online models and extend it to the bipartite setting.