Eric Blais

Assistant Professor
David R. Cheriton School of Computer Science
University of Waterloo


Winter 2019

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.



Abhinav Bommireddi, PhD candidate

  • Nathan Harms, PhD candidate

  • Amit Levi, PhD candidate

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

  • 2017

  • Sean Harrap, URA

  • David Urbanik, Undergraduate thesis

  • 2016

  • Wilson Cheang, NSERC USRA

  • Sally Dong, URA

  • 2015

  • Bai Li, URA

  • Ron Meng, URA

  • 2016

    Tom Gur (Weizmann Institute)

  • Nicolas Resch (CMU)

  • Research

    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.

    Journal & Conference Publications

    A characterization of constant-sample testable properties
    with Y. Yoshida
    To appear in Random Structures & Algorithms.

    Tolerant junta testing and the connection to submodular optimization and function isomorphism
    with C. Canonne, T. Eden, A. Levi, and D. Ron
    SODA 2018.

    I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making
    with S. Rahman, M. Aliakbarpour, H. Kong, K. Karahalios, A. Parameswaran, and R. Rubinfeld
    PVLDB 10(11), 2017

    Distribution testing lower bounds via reductions from communication complexity
    with C. Canonne and T. Gur
    CCC 2017
    (ECCC report TR16-168, 2016.)

    A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
    with J. Guo, K. Czarnecki, and P. van Beek
    Canadian Conference on AI 2017.

    Testing submodularity and other properties of valuation functions
    with A. Bommireddi
    ITCS 2017.

    Learning and testing junta distributions
    with M. Aliakbarpour and R. Rubinfeld
    COLT 2016.

    Detecting performance-relevant feature interactions by theoretical analysis of Boolean functions
    with Y. Zhang, J. Guo, K. Czarnecki, and H. Yu
    SPLC 2016.

    A polynomial lower bound for testing monotonicity
    with A. Belov
    STOC 2016.
    (arXiv report 1511.05053.)

    Approximating Boolean functions with depth-2 circuits
    with L.-Y. Tan
    SIAM Journal on Computing 44(6), 2015.
    (Conference version in CCC 2013. ECCC report TR13-051.)

    Quantum algorithm for monotonicity testing on the hypercube
    with A. Belov
    Theory of Computing 11(16), 2015.
    (arXiv report 1503.02868.)

    Performance prediction of configurable software systems by Fourier learning
    with Y. Zhang, J. Guo, and K. Czarnecki
    ASE 2015.

    Learning circuits with few negations
    with C. Canonne, I. Carboni Oliveira, R. Servedio, and L.-Y. Tan
    RANDOM 2015.
    (arXiv report 1410.8420.)

    Rapid sampling for visualizations with ordering guarantees
    with A. Kim, A. Parameswaran, P. Indyk, S. Madden, and R. Rubinfeld
    PVLDB 8(5), 2015.
    (arXiv report 1412.3040.)

    Partially symmetric functions are efficiently isomorphism-testable
    with A. Weinstein and Y. Yoshida
    SIAM Journal on Computing 44(2), 2015.
    (Conference version in FOCS 2012. arXiv report 1112.5741.)

    The information complexity of Hamming distance
    with J. Brody and B. Ghazi
    RANDOM 2014.

    On DNF approximators for monotone Boolean functions
    with J. Håstad, R. Servedio, and L.-Y. Tan
    ICALP 2014.

    Lower bounds for testing properties of functions on hypergrid domains
    with S. Raskhodnikova and G. Yaroslavtsev
    CCC 2014.
    (ECCC report TR13-036.)

    Hypercontractivity via the entropy method
    with L.-Y. Tan
    Theory of Computing, Special issue: Analysis of Boolean Functions, 2013.

    Nearly tight bounds for testing function isomorphism
    with N. Alon, S. Chakraborty, D. Garcia-Soriano, and A. Matsliah
    SIAM Journal on Computing 42(2), 2013.

    Semi-strong coloring of intersecting hypergraphs
    with A. Weinstein and Y. Yoshida
    Combinatorics, Probability, and Computing, 2013.
    (arXiv report 1203.2868.)

    Active property testing
    with M.-F. Balcan, A. Blum, and L. Yang
    FOCS 2012.
    (arXiv report 1111.0897.)

    Tight bounds for testing k-linearity
    with D. Kane
    RANDOM 2012.

    Property testing lower bounds via communication complexity
    with J. Brody and K. Matulef
    Computational Complexity, 2012.
    (Conference version in CCC 2011. ECCC report TR11-045.)

    Testing boolean function isomorphism
    with N. Alon
    RANDOM 2010.

    Lower bounds for testing function isomorphism
    with R. O'Donnell
    CCC 2010.

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

    Testing juntas nearly optimally
    STOC 2009.

    Improved bounds for testing juntas
    RANDOM 2008.

    Polynomial regression under arbitrary product spaces
    with R. O'Donnell and K. Wimmer
    Machine Learning, 2010.
    (Conference version in COLT 2008.)

    Gene maps linearization using genomic rearrangement distances
    with G. Blin, D. Hermelin, P. Guillon, M. Blanchette, and N. El-Mabrouk
    Journal of Computational Biology, 2007.
    (Conference version in RECOMB Comparative Genomics 2006.)

    On the inference of parsimonious indel scenarios
    with L. Chindelevitch, Z. Li, and M. Blanchette
    Journal of Bioinformatics and Computational Biology, 2006.


    An inequality for the Fourier spectrum of parity decision trees
    with L.-Y. Tan and A. Wan
    arXiv report 1506.01055, 2015.

    Longest common subsequences in sets of permutations
    with P. Beame and D.-T. Huynh-Ngoc
    arXiv report 0904.1615, 2009.

    Other Publications

    Something for (almost) nothing: new advances in sublinear-time algorithms
    with R. Rubinfeld
    Invited chapter in Handbook of Big Data, CRC Press, 2016

    Testing juntas and related properties of Boolean functions
    Invited chapter in Encyclopedia of Algorithms, Springer, 2015

    Testing properties of boolean functions
    Ph.D. Thesis, Carnegie Mellon University, 2012

    Testing juntas: a brief survey
    Invited chapter in Property Testing: Current Research and Surveys, Springer, 2011.

    Common substrings in random strings
    Master's Thesis, McGill University, 2006
    (Conference version with M. Blanchette in CPM 2006.)

    Graphics processing method and system
    with I. Ameline
    U.S. Patent 8,744,184, 2014. (Filed in 2004.)



    DC 3122

    Mailing address
    David R. Cheriton School of Computer Science
    University of Waterloo
    200 University Avenue West
    Waterloo, ON N2L 3G1