LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

65 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 5 m
Compared with MathematicsShorter than 69%
Source channelInstitute for Advanced Study (YouTube)