Data Structures Meet Circuits and Cryptography

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.

Bio:  Alexander Golovnev is a Rabin postdoctoral fellow at Harvard University. Prior to this, he was a postdoctoral fellow at Columbia University, and a Research Scientist at Yahoo Research. He received his PhD from the Courant Institute of Mathematical Sciences at New York University.

Alexander’s research interests lie broadly in computational complexity, algorithms, learning theory, cryptography and pseudorandomness, with a focus on proving lower bounds for various computational models.