
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
Guy Blanc, from Stanford University, presents a seminar at the Institute for Advanced Study on two linked results in learning theory and complexity theory. On the learning side, he examines smooth boosting algorithms, which avoid overweighting any single training example and are used for robustness, privacy, and reproducibility, showing that their sample complexity overhead is provably optimal and distinct from distribution-independent boosting. On the complexity side, he connects this to Impagliazzo's hardcore theorem, which shows that a function mildly hard for small circuits contains a subset of inputs that is extremely hard for somewhat smaller circuits. Answering a question posed by Luca Trevisan, Blanc proves that the loss in circuit size inherent to all known proofs of the hardcore theorem is unavoidable and already optimal. The talk is technical, aimed at researchers in theoretical computer science and discrete mathematics, delivered as part of the IAS Computer Science/Discrete Mathematics Seminar.