Meta-Complexity Seminar

Title: Pseudorandom Self-Reductions for NP-Complete Problems

Speaker: Robert Robere (McGill University)

Abstract: A major open problem in complexity theory is whether or not we can base the average-case hardness of NP on the worst-case hardness of NP — that is, whether or not NP-Complete languages admit random self-reductions. It is famously known that several “numerical” problems (which are unlikely to be NP-Complete) admit such reductions, such as the problem of computing the permanent of a matrix. Furthermore, classic results of Fortnow-Lund and Bogdanov-Trevisan argue that NP does not admit random self-reductions which are “non-adaptive”, in that the later random queries cannot depend on earlier random queries, unless the polynomial-time hierarchy collapses. In a recent work, Hirahara and Santhanam introduced the notion of pseudorandom self-reductions, where we only have to reduce to a distribution that is computationally indistinguishable from the uniform distribution. They showed that the Minimum Circuit Size Problem (MCSP) admits such a reduction — a result which is quite striking, given that it is unknown whether or not MCSP is NP-Complete — and suggested that this further distinguished MCSP from other NP-Complete problems in light of the known “no-go” results discussed above.

We show that, in spite of this intuition, NP-Complete problems can admit pseudorandom self-reductions. In particular, we show that the Clique problem admits a pseudorandom self-reduction, assuming a variant of the planted clique conjecture. In this talk we will present our reduction and some generalizations, and discuss further open problems.

This is based on joint work with Reyad Abed Elrazik, Assaf Schuster, and Gal Yehuda.