Assistant Professor

David R. Cheriton School of Computer Science

University of Waterloo

eric.blais@uwaterloo.ca

**Communication complexity (CS 860)**

Communication complexity is an elegant area of theoretical computer science that has served to prove optimality results in a wide variety of areas, including data structures, streaming algorithms, circuit complexity, distributed computing, etc. In this course, we will learn all about this topic, its connections to various branches of mathematics, and its applications.

**Models of computation (CS 365)**

This class provides an intensive introduction to the theory of computation. We will cover introductory and more advanced topics in automata theory, computability theory, and complexity theory.

**Algorithms (CS 341)**

We will study efficient algorithms, effective algorithm design techniques, and approaches to handling situations in which no feasible algorithms are known. The course is intended to give the student experience in program design and to emphasize both pragmatic and mathematical aspects of program efficiency.

**Algorithm Design and Analysis (CS 466/666)**

We will study five powerful tools in the design and analysis of algorithms: randomization, approximation, sketching, formulation as constraint satisfaction problems, and amortized analysis. Furthermore, we will also introduce techniques for establishing the limits of efficient algorithms.

**Analysis of Boolean functions (CS 798-004)**

We will explore how the Fourier analysis of Boolean functions can be used to prove a variety of results in learning theory, sublinear-time algorithms, circuit complexity, and other areas of computer science.

**Models of computation (CS 365)**

This class provides an intensive introduction to the theory of computation. We will cover introductory and more advanced topics in automata theory, computability theory, and complexity theory.

**Algorithm Design and Analysis (CS 466/666)**

In this class, we will explore algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and application.

**Complexity of computational problems (CS 489)**

This class provides an introduction to the topic of establishing the absolute
limits of algorithms in various computational models.
In particular, we will explore how to prove lower bounds on the amount of time and space
required to solve computational problems with randomized algorithms, parallel
algorithms, and approximation algorithms.

**Concentration inequalities in computer science (CS 860)**

Concentration inequalities are powerful mathematical tools with many applications
in computer science. In this course, we will introduce these inequalities
and develop expertise in applying them to problems in the analysis of randomized algorithms and in complexity theory.

**Models of computation (CS 365)**

This class provides an intensive introduction to the theory of computation. We will cover introductory and more advanced topics in automata theory, computability theory, and complexity theory.

**Sublinear-time algorithms (CS 860)**

In this class, we will explore the following fundamental question:
what problems can we solve when we are only allowed to examine a very small fraction of the input?
As we will see, this question leads to many deep results and intriguing open problems in different areas of theoretical computer science, including complexity theory, learning theory, property testing, error-correcting codes, and interactive proofs.

**Abhinav Bommireddi**, PhD candidate

**Nathan Harms**, PhD candidate

**Amit Levi**, PhD candidate

**Kaleb Alway**, MMath candidate (coadvised with Semih Salihoglu)

**Sean Harrap**, URA

**David Urbanik**, Undergraduate thesis

**Wilson Cheang**, NSERC USRA

**Sally Dong**, URA

**Bai Li**, URA

**Ron Meng**, URA

**Tom Gur** (Weizmann Institute)

**Nicolas Resch** (CMU)

My research is in theoretical computer science with an emphasis on the complexity of boolean functions and sublinear-time algorithms. I am particularly interested in the interplay between computer science, combinatorics, and information theory.

with Y. Yoshida

To appear in

with C. Canonne, T. Eden, A. Levi, and D. Ron

SODA 2018.

with S. Rahman, M. Aliakbarpour, H. Kong, K. Karahalios, A. Parameswaran, and R. Rubinfeld

with C. Canonne and T. Gur

CCC 2017

(ECCC report TR16-168, 2016.)

with J. Guo, K. Czarnecki, and P. van Beek

Canadian Conference on AI 2017.

with A. Bommireddi

ITCS 2017.

with M. Aliakbarpour and R. Rubinfeld

COLT 2016.

with Y. Zhang, J. Guo, K. Czarnecki, and H. Yu

SPLC 2016.

with A. Belov

STOC 2016.

(arXiv report 1511.05053.)

with L.-Y. Tan

(Conference version in CCC 2013. ECCC report TR13-051.)

with A. Belov

(arXiv report 1503.02868.)

with Y. Zhang, J. Guo, and K. Czarnecki

ASE 2015.

with C. Canonne, I. Carboni Oliveira, R. Servedio, and L.-Y. Tan

RANDOM 2015.

(arXiv report 1410.8420.)

with A. Kim, A. Parameswaran, P. Indyk, S. Madden, and R. Rubinfeld

(arXiv report 1412.3040.)

with A. Weinstein and Y. Yoshida

(Conference version in FOCS 2012. arXiv report 1112.5741.)

with J. Brody and B. Ghazi

RANDOM 2014.

with J. Håstad, R. Servedio, and L.-Y. Tan

ICALP 2014.

with S. Raskhodnikova and G. Yaroslavtsev

CCC 2014.

(ECCC report TR13-036.)

with L.-Y. Tan

with N. Alon, S. Chakraborty, D. Garcia-Soriano, and A. Matsliah

with A. Weinstein and Y. Yoshida

(arXiv report 1203.2868.)

with M.-F. Balcan, A. Blum, and L. Yang

FOCS 2012.

(arXiv report 1111.0897.)

with D. Kane

RANDOM 2012.

with J. Brody and K. Matulef

(Conference version in CCC 2011. ECCC report TR11-045.)

with N. Alon

RANDOM 2010.

with R. O'Donnell

CCC 2010.

with J. Aspnes, M. Demirbas, R. O'Donnell, A. Rudra, and S. Uurtamo

ALGOSENSORS 2010.

STOC 2009.

RANDOM 2008.

with R. O'Donnell and K. Wimmer

(Conference version in COLT 2008.)

with G. Blin, D. Hermelin, P. Guillon, M. Blanchette, and N. El-Mabrouk

(Conference version in RECOMB Comparative Genomics 2006.)

with L. Chindelevitch, Z. Li, and M. Blanchette

with L.-Y. Tan and A. Wan

arXiv report 1506.01055, 2015.

with P. Beame and D.-T. Huynh-Ngoc

arXiv report 0904.1615, 2009.

with R. Rubinfeld

Invited chapter in

Invited chapter in

Ph.D. Thesis, Carnegie Mellon University, 2012

Invited chapter in

Master's Thesis, McGill University, 2006

(Conference version with M. Blanchette in CPM 2006.)

with I. Ameline

U.S. Patent 8,744,184, 2014. (Filed in 2004.)

- eric.blais@uwaterloo.ca
- Office
- DC 3122
- Mailing address
- David R. Cheriton School of Computer Science

University of Waterloo

200 University Avenue West

Waterloo, ON N2L 3G1

Canada