SILO Seminar

Quentin Berthet from Caltech shows how the hypotheses from theoretical computer science on the hardness of some problems in average case can give a better understanding of algorithmic limitations for high-dimensional statistical problems. Several results related to the planted clique problem are shown and a problem is studied involving random satisfiability formulas.