Derandomization, tutorial - part 1: Pseudo-randomness from hardness
De Valentine Kabanets
Et si SAT était vraiment difficile? Quelques conséquences des hypothèses ETH et SETH
De Bruno Escoffier
Apparaît dans la collection : Schlumberger workshop - Computational and statistical trade-offs in learning
I will explore the notion of constraints on learning procedures, and discuss the impact that they can have on statistical precision. This is inspired by real-life concerns such as limits on time for computation, on reliability of observations, or communication between agents. I will show how these constraints can be shown to have a concrete cost on the statistical performance of these procedures, by describing several examples.