[Colloq] Talk - Eric Blais - Tuesday, April 15, 10:00 AM, 366 WVH - Sublinear-time algorithms for massive datasets

[Jessica Biron]

TITLE: Sublinear-time algorithms for massive datasets 



SPEAKER: Eric Blais (MIT) 



TIME/LOCATION: Tuesday, April 15, 10:00 AM, 366 WVH 



ABSTRACT: 



Massive datasets are becoming pervasive in science and in industry. Designing algorithms and computational systems that can deal with these datasets is one of the great challenges of computer science over the coming decades. 



One particularly promising tool for meeting this challenge is the rapidly developing field of sublinear-time algorithms--algorithms whose running times are asymptotically smaller than the size of their inputs. The construction of such algorithms, however, poses a unique challenge: to run in sublinear time, an algorithm must only inspect a tiny fraction of its input data before producing its output. 



In this talk, we will introduce new sublinear-time algorithms for fundamental problems on massive datasets, we will present new techniques for establishing the limits of such algorithms, and we will explore connections between this field of research and other areas of computer science. 





BIOGRAPHY: 



Eric Blais is a Simons Postdoctoral Fellow with the Theory of Computing group at MIT. His research is in theoretical computer science with a particular emphasis on sublinear-time algorithms and the complexity of boolean functions. Dr. Blais completed his Ph.D. under the supervision of Ryan O'Donnell at Carnegie Mellon University in early 2012. Prior to that, he completed a M.Sc. at McGill University and a B.Math. at the University of Waterloo, both in computer science. 



Host: Rajmohan Rajaraman