Special Colloquium
Alexander Golovnev
Harvard University
Data Structures Meet Circuits and Cryptography
Abstract: In this talk we will discuss the state of the art in the field of data structure lower bounds and surprising connections between such lower bounds, circuit complexity, and cryptography. Proving such limitations on data structures and circuits has been a fundamental research endeavor for several decades, with connections to efficient parallel computation and the P-vs-NP question. Despite much effort, our best lower bounds in both fields have remained unchanged since the 1980s.
We show a surprising connection between both fields, offering an explanation for this lack of progress. Specifically, we show that any improvement on the best known lower bound for a (linear) data structure problem would imply new circuit lower bounds, and vice versa. Our proof uses a new connection between additive and multiplicative sparse matrix factorizations.
We continue this line of research by showing that data structure lower bounds for a specific class of problems are equivalent to a certain kind of cryptography. We use this connection to construct surprising (crypto-inspired) data structures for the 3-SUM problem, refuting a data structure variant of the 3SUM conjecture due to Goldstein et al.
Friday January 31, 2020 at 10:00 AM in 636 SEO