Sublinear-Time Algorithms

10 Nov
Friday, 11/10/2017 10:30am to 11:30am
Computer Science Building, Room 142
Special Event

Distinguished Theory Colloquium

Massive datasets are becoming increasingly common. What useful computations can be performed on a dataset  when reading all of it is prohibitively expensive? This question, fundamental to several fields, is at the heart of the research area, called sublinear-time algorithms, that has provided important insights into fast approximate computation.

In this talk, we will consider types of computational tasks central to sublinear-time algorithms:  testing, learning, and approximation. We will see examples of sublinear-time algorithms in several domains. The algorithms themselves are typically simple and efficient, but their analysis requires insights into basic combinatorial, algebraic, and geometric questions. We will also discuss new directions in sublinear-time algorithms, including new computational tasks, new measures for accuracy guarantees, and new models for data access. These directions enable applications of sublinear-time algorithms in privacy, analysis of real-valued data, and situations where the data is noisy or incomplete.

Sofya Raskhodnikova is a professor of Computer Science at Boston University. Prior to joining BU, she was a faculty member at Penn State from 2007 to 2017. She received her Ph.D. from MIT. She held postdoctoral and visiting positions at the Hebrew University of Jerusalem, the Weizmann Institute of Science, the Institute for Pure and Applied Mathematics at UCLA, Boston University, and Harvard University.

Dr. Raskhodnikova works in the areas of randomized and approximation algorithms. Her main interest is the design and analysis of sublinear-time algorithms for combinatorial problems. She has also made important contributions to data privacy.

Faculty Host
: