Skip to yearly menu bar Skip to main content


Invited Talk

Sketching: core tools, learning-augmentation, and adaptive robustness

Jelani Nelson

Moderator : Moritz Hardt

Hall E (level 1)

Abstract:

'Sketches' of data are memory-compressed summarizations that still allow answering useful queries, and as a tool have found use in algorithm design, optimization, machine learning, and more. This talk will give an overview of some core sketching tools and how they work, including recent advances. We also discuss a couple newly active areas of research, such as augmenting sketching algorithms with learned oracles in a way that provides provably enhanced performance guarantees, and designing robust sketches that maintain correctness even in the face of adaptive adversaries.