Sublinear-Time Algorithms
Sofya Raskhodnikova - School of Electrical Engineering and Computer Science, Pennsylvania State University
March 17, 2017, 2:30 p.m. - March 17, 2017, 3:30 p.m.
ENGMC 12
Abstract:
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.
Speaker Bio: Sofya Raskhodnikova is an associate professor of Computer Science and Engineering at Penn State. She received her Ph.D. from MIT. Prior to joining Penn State in 2007, she was a postdoctoral fellow at the Hebrew University of Jerusalem and the Weizmann Institute of Science. She has held visiting positions at the Institute for Pure and Applied Mathematics at UCLA, Boston University, and Harvard University. She is a recipient of the NSF CAREER award.
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.
ALL ARE WELCOME !!!
