Below √n, no efficient algorithm finds a planted clique in a random graph. The hardness assumption behind sparse PCA, community detection and average-case crypto.
The Problems
Not schoolwork — the questions that resisted Erdős, Hilbert, and everyone since. The club keeps three shelves: what is still open, what AI recently settled, and what took humanity centuries.
Tagged average-case-complexity — 1 entry. Clear