Data Structures Meet Circuits and Cryptography

Assistant Professor Alexander Golovnev, Georgetown University
Contact Person
Dr Kuldeep S. MEEL, NUS Presidential Young Professor, School of Computing

13 Jul 2022 Wednesday, 04:00 PM to 05:00 PM

SR3 (COM1-02-12) and via Zoom (Hybrid)

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.

Alexander Golovnev is an Assistant Professor at Georgetown University. Prior to this, he was a Rabin postdoctoral fellow at Harvard University, a postdoctoral fellow at Columbia University, and a Research Scientist at Yahoo Research. He received his Ph.D. 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.