Information for

Assistant Professor

Research interests

Professor Blais's research interests are in the areas of algorithms and complexity theory. His research is concerned with the following question: what tasks can algorithms accomplish when they are only allowed to examine a tiny fraction of their input? This question is particularly relevant given the massive datasets generated by new data collection technologies in many scientific areas; in this setting, any efficient algorithm must run in time that is sublinear in the size of this input data, and so it only has time to examine some of the data. This research also has applications in many other areas of computer science, including property testing, locally decodable error-correcting codes, machine learning, compressed sensing, and complexity theory.

Much of the recent work of Professor Blais has focused on the situation where the algorithm's input represents a Boolean function and the algorithm seeks to determine if the function is "simple" or not, according to some appropriate notion of simplicity. This general situation captures many fundamental computational tasks. By combining algorithmic design methods with tools from the analysis of Boolean functions and extremal combinatorics, this research has shown that many such tasks can be done efficiently with algorithms that inspect only a constant number of bits of the input.

Degrees and awards

BMath (Waterloo), MSc (McGill), PhD (Carnegie Mellon)

Simons Foundation Postdoctoral Fellow, MIT (2012-2014)

Representative publications

Eric Blais and Li-Yang Tan. Approximating boolean functions with depth-2 circuits. In Proc. 28th Annual IEEE Conference on Computational Complexity (CCC), pages 74–85, 2013.

Eric Blais, Amit Weinstein, and Yuichi Yoshida. Partially symmetric functions are isomorphism testable. In Proc. IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 551–560, 2012.

Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang. Active property testing. In Proc. IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 21–30, 2012

Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. Computational Complexity, 21(2):311–358, 2012.

Eric Blais. Testing juntas nearly optimally. In Proc. 41st Annual ACM Symposium on Theory of Computing (STOC), pages 151–158, 2009.

University of Waterloo
Contact information: