Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to
almost any known cryptographic object. Prior candidate IO constructions were based on …

A precise high-dimensional asymptotic theory for boosting and minimum-l1-norm
interpolated classifiers Page 1 The Annals of Statistics 2022, Vol. 50, No. 3, 1669–1695 …

Computational barriers to estimation from low-degree polynomials Page 1 The Annals of
Statistics 2022, Vol. 50, No. 3, 1833–1858 https://doi.org/10.1214/22-AOS2179 © Institute of …

A long-standing open question in computational learning theory is to prove NP-hardness of
learning efficient programs, the setting of which is in between proper learning and improper …

We survey the average-case complexity of problems in NP. We discuss various notions of
good-on-average algorithms, and present completeness results due to Impagliazzo and …

There are significant obstacles to establishing an equivalence between the worst-case and
average-case hardness of NP: Several results suggest that black-box worst-case to …

A one-way function is a function that is easy to compute but hard to invert* on average*. We
establish the first characterization of a one-way function by* worst-case* hardness …

We present the first natural $\NP $-complete problem whose average-case hardness wrt the
uniform distribution over instances is\emph {equivalent} to the existence of one-way …

Whether one-way functions (OWF) exist is arguably the most important problem in
Cryptography, and beyond. While lots of candidate constructions of one-way functions are …

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and
only if the (polynomial-) time-bounded Kolmogorov complexity, ${\rm K}^ t $, is bounded …