Computer science professor Omri Weinstein wins NSF Career Award

New York, NY–Feb 28 2019–Omri Weinstein, assistant professor of computer science at Columbia Engineering, has won a National Science Foundation CAREER Award for his project, “Information Theoretic Methods in Data Structures.” The five-year, $500,000 award is one of the NSF’s most prestigious honors for faculty at or near the beginning of their careers.

Weinstein, who joined Columbia Engineering in 2017, is interested in the interplay between information theory and data structures, and more broadly in applications of information theory to computational complexity and interactive computation.

“I am very pleased to have been recognized by the NSF and to have its support for my research,” said Weinstein.

Data structures are the backbone of algorithm design and information retrieval, and underlie the performance of countless industrial-scale applications, from Cloud storage and machine learning, to internet routing and road navigation. As such, understanding what data structures can and cannot compute efficiently is a fundamental question in both theory and practice. This question is exacerbated by the proliferation of data being uploaded and analyzed on remote data-centers, challenging the traditional design of large-scale databases and storage algorithms.

Weinstein’s NSF project focuses on two primary themes. The first theme is developing new mathematical tools for proving unconditional lower bounds on the operational time and memory consumption of data structures, and the second is exploring the interplay between algorithmic information theory and data structures in large-scale storage applications. In particular, Weinstein hopes to develop space-efficient and I/O-efficient data structures for information retrieval, focusing on the tradeoff between compression and search over massive correlated datasets, such as genomic and financial databases.

“With this NSF support, I hope to develop new techniques for better analyzing the operational time of static and dynamic data structures, and along the way, to discover new connections between data structures and other areas of complexity theory and mathematics (e.g., streaming, algebraic geometry, codes, and circuit lower bounds),” said Weinstein. Weinstein’s new paradigm of “locally-decodable data compression,” outlined in his project proposal, lays down the theoretical foundation for scaling up modern digital storage technology.

###