Data Structures Meet Cryptography - 3SUM with Preprocessing

Explore the intersection of data structures and cryptography in this 26-minute ACM conference talk. Delve into the 3SUM problem with preprocessing, examining both algorithmic and data structure approaches. Learn about inverting functions and bijections, and discover new data structure lower bounds. Gain insights into static data structures, cryptography with preprocessing, and the equivalence between 3SUM-indexing and other computational challenges.

Intro
OUTLINE
STATIC DATA STRUCTURES. DEFINITION
CRYPTOGRAPHY WITH PREPROCESSING
3SUM. ALGORITHMIC VERSION
3SUM. DATA STRUCTURE VERSION
INVERTING A FUNCTION
INVERTING A BIJECTION
DS FOR 3SUM-INDEXING
EQUIVALENCE
NEW DS LOWER BOUNDS