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.
Data Structures Meet Cryptography - 3SUM with Preprocessing
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
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
Taught by
Association for Computing Machinery (ACM)
Related Courses
-
Polynomial Data Structure Lower Bounds in the Group Model
-
Theory Seminar - On Linear Data Structures and Matrix Rigidity, Sivaramakrishnan Ramamoorthy
-
Bandwidth-Hard Functions - Reductions and Lower Bounds
-
How Much Data Is Sufficient to Learn High-Performing Algorithms?
-
On the Role of Data Structure in High-Dimensional Learning
