Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdős-Rényi random graph with a k-clique planted for $k << n^{1/2}$. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability $k^2/n$ for any $k \le n^{1/2}$. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than $k^2/n$ *if and only if* the planted clique conjecture holds.

Joint work with Nobutaka Shimizu. Paper: https://eccc.weizmann.ac.il/report/2024/058/

Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems (CSP), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete.

Inspired and emboldened by this, one might speculate a polymorphic principle in more general contexts, with symmetries in the solution space governing efficient algorithms. Beginning with some background on CSP and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP” (PCSP) where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring). We will provide glimpses of the emerging polymorphic theory characterizing the (in)tractability of interesting classes of PCSP as well as the ability of natural classes of algorithms to solve them.