Speaker: Xiaobo Yang (PKU)

Time: 16:00-17:00 p.m., August 4, 2023, GMT+8

Venue: Tecent Meeting ID: 723 1564 5542

Abstract:

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.

Source: School of Mathematical Sciences