机器学习与数据科学博士生系列论坛（第五十四期）—— Average-Case Reduction for Information-Computation Tradeoffs

摘要：
Information-Computation tradeoff is a phenomenon where the most efficient algorithm used by people to solve statistical problems exhibits a non-negligible gap from what is considered information-theoretically optimal. One of the representative problems illustrating this tradeoff is the Planted Clique (PC) problem, which involves hypothesis testing between the distribution of an Erdős–Rényi graph $G(n,1/2)$ and the distribution of $G(n,1/2)$ with an unknown planted $k$-clique. When $k>2\log n$, the testing becomes information-theoretically detectable. However, the best polynomial-time algorithm can only solve for $k >> \sqrt{n}$.

To comprehend this phenomenon, A long line of work attempts to establish complexity lower bounds under different restricted models of computation, such as the Statistical Query model, the sum-of-squares hierarchy, and the low-degree polynomial model, etc. On the other hand, researchers explore the relationships and connections between different computational hardnesses by establishing reductions among these average-case problems, providing strong evidence for their claims.

In this talk, we introduce average-case reduction for Information-Computation tradeoffs through several pedagogical examples. This serves as a starting point towards understanding the theory.

论坛简介：该线上论坛是由张志华教授机器学习实验室组织，每两周主办一次（除了公共假期）。论坛每次邀请一位博士生就某个前沿课题做较为系统深入的介绍，主题包括但不限于机器学习、高维统计学、运筹优化和理论计算机科学。