标题： 关于植 clique 的最优区分器 显示英文标题

标题： On optimal distinguishers for Planted Clique

摘要： 在区分问题中，输入是从两个分布中的一个抽取的样本，算法的任务是识别来源分布。 区分算法的性能通过其优势来衡量，即其成功概率相对于随机猜测的增量。 一个经典的区分问题是植入团问题，其中输入是从以下两种模型之一抽取的图：$G(n,1/2)$—— 标准的Erdős-Rényi模型，或$G(n,1/2,k)$—— 在一个随机选取的$k$个顶点上植入了一个团的Erdős-Rényi模型。 植入团假设断言，当$k=n^{1/2-\Omega(1)}$时，高效的算法无法获得优于某个绝对常数（例如$1/4$）的优势。 在本工作中，我们旨在精确理解在植入团问题上，高效算法能够实现的最佳区分优势。 我们在植入团假设下得出以下结果： 1. 低次多项式的最优性：没有高效的算法可以超越最优的低次多项式的优势。 具体来说，这意味着任何高效算法的优势最多为$(1+o(1))\cdot k^2/(\sqrt{\pi}n)$，这在一种简单的边计数算法达到该界限的情况下是最优的。 2. 更难的植入分布：存在一个可高效采样的分布$\mathcal{P}^*$，它在包含$k$-clique 的图上进行支持，使得没有任何高效算法能以优势$n^{-d}$区分$\mathcal{P}^*$与$G(n,1/2)$，对于任意大的常数$d$。 换句话说，存在其他更难的植入分布，它们比$G(n,1/2,k)$要困难得多。 在此过程中，我们证明了一个针对低次数多项式的一类广泛分布的构造性硬核引理。 这个结果的应用范围远超植入团问题，可能具有独立的兴趣。 显示英文摘要

摘要： In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a distinguishing algorithm is measured by its advantage, i.e., its incremental probability of success over a random guess. A classic example of a distinguishing problem is the Planted Clique problem, where the input is a graph sampled from either $G(n,1/2)$ -- the standard Erd\H{o}s-R\'{e}nyi model, or $G(n,1/2,k)$ -- the Erd\H{o}s-R\'{e}nyi model with a clique planted on a random subset of $k$ vertices. The Planted Clique Hypothesis asserts that efficient algorithms cannot achieve advantage better than some absolute constant, say $1/4$, whenever $k=n^{1/2-\Omega(1)}$. In this work, we aim to precisely understand the optimal distinguishing advantage achievable by efficient algorithms on Planted Clique. We show the following results under the Planted Clique hypothesis: 1. Optimality of low-degree polynomials: No efficient algorithm can beat the advantage the optimal low-degree polynomial. Concretely, this means that the advantage of any efficient algorithm is at most $(1+o(1))\cdot k^2/(\sqrt{\pi}n)$, which is optimal in light of a simple edge-counting algorithm achieving this bound. 2. Harder planted distributions: There is an efficiently sampleable distribution $\mathcal{P}^*$ supported on graphs containing $k$-cliques such that no efficient algorithm can distinguish $\mathcal{P}^*$ from $G(n,1/2)$ with advantage $n^{-d}$ for an arbitrarily large constant $d$. In other words, there exist alternate planted distributions that are much harder than $G(n,1/2,k)$. Along the way, we prove a constructive hard-core lemma for a broad class of distributions with respect to low-degree polynomials. This result is applicable much more widely beyond Planted Clique and might be of independent interest.