Research
Publications
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais and Cameron Seth
STOC 2024 | arXiv
Testing and Learning Convex Sets in the Ternary Hypercube
Hadley Black, Eric Blais, and Nathaniel Harms
ITCS 2024 | arXiv
A New Minimax Theorem for Randomized Algorithms
Shalev Ben-David and Eric Blais
Journal of the ACM, 2023 | FOCS 2020 | arXiv
Testing Graph Properties with the Container Method
Eric Blais and Cameron Seth
FOCS 2023 | arXiv
Randomised Composition and Small-Bias Minimax
Shalev Ben-David, Eric Blais, Mika Göös, and Gilbert Maystre
FOCS 2022 | arXiv | ECCC
A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs and Eric Blais
SIAM Journal on Computing, 2021 | STOC 2016 | arXiv
VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto Jr., and Nathaniel Harms
STOC 2021 | arXiv
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing
Kaleb Alway, Eric Blais, and Semih Salihoglu
ICDT 2021 | arXiv
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David and Eric Blais
FOCS 2020 | arXiv
On Testing and Robust Characterizations of Convexity
Eric Blais and Abhinav Bommireddi
RANDOM 2020
Testing Convexity of Functions over Finite Domains
Aleksandrs Belov, Eric Blais, and Abhinav Bommireddi
SODA 2020 | arXiv
A Characterization of Constant-Sample Testable Properties
Eric Blais and Yuichi Yoshida
Random Structures & Algorithms, 2019 | arXiv | ECCC
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément Canonne, Talya Eden, Amit Levi, and Dana Ron
ACM Transactions on Computation Theory, 2019 | SODA 2018 | arXiv | ECCC
Optimal Separation and Strong Direct Sum for Randomized Query Complexity
Eric Blais and Joshua Brody
CCC 2019 | arXiv
Distribution Testing Lower Bounds via Reductions from Communication Complexity
Eric Blais, Clément Canonne, and Tom Gur
ACM Trans. Comput. Theory, 2019 | CCC 2017 | ECCC
Testing Submodularity and Other Properties of Valuation Functions
Eric Blais and Abhinav Bommireddi
ITCS 2017 | arXiv
I’ve Seen Enough: Incrementally Improving Visualizations to Support Rapid Decision Making
Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya Parameswaran, and Ronitt Rubinfeld
VLDB, 2017
A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
Jianmei Guo, Eric Blais, Krzysztof Czarnecki, and Peter van Beek
Canadian AI 2017
A Mathematical Model of Performance-Relevant Feature Interactions
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki, and Huiqun Yu
SPLC 2016
Learning and Testing Junta Distributions
Maryam Aliakbapour, Eric Blais, and Ronitt Rubinfeld
COLT 2016
Quantum Algorithm for Monotonicity Testing on the Hypercube
Aleksandrs Belovs and Eric Blais
Theory of Computing, 2015 | arXiv
Performance Prediction of Configurable Software Systems by Fourier Learning
Yi Zhang, Jianmei Guo, Eric Blais, and Krzysztof Czarnecki
ASE 2015
Approximating Boolean Functions with Depth-2 Circuits
Eric Blais and Li-Yang Tan
SIAM J. Computing, 2015 | CCC 2013 | ECCC
Learning Circuits with Few Negations
Eric Blais, Clément Canonne, Igor Oliveira, Rocco Servedio, and Li-Yang Tan
RANDOM 2015 | arXiv
An Inequality for the Fourier Spectrum of Parity Decision Trees
Eric Blais, Li-Yang Tan, and Andrew Wan
arXiv
Partially Symmetric Functions Are Efficiently Isomorphism Testable
Eric Blais, Amit Weinstein, and Yuichi Yoshida
SIAM J. Computing, 2015 | FOCS 2012 | arXiv
Rapid Sampling for Visualizations with Ordering Guarantees
Albert Kim, Eric Blais, Aditya Parameswaran, Piotr Indyk, Samuel Madden, and Ronitt Rubinfeld
VLDB, 2015 | arXiv
The Information Complexity of Hamming Distance
Eric Blais, Joshua Brody, and Badih Ghazi
RANDOM 2014
On DNF Approximators for Monotone Boolean Functions
Eric Blais, Johan Håstad, Rocco Servedio, and Li-Yang Tan
ICALP 2014
Lower Bounds for Testing Properties of Functions over Hypergrid Domains
Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev
CCC 2014 | ECCC
Semi-Strong Colouring of Intersecting Hypergraphs
Eric Blais, Amit Weinstein, and Yuichi Yoshida
Combinatorics, Probability & Computing, 2014
Hypercontractivity Via the Entropy Method
Eric Blais and Li-Yang Tan
Theory of Computing, 2013
Nearly Tight Bounds for Testing Function Isomorphism
Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, and Arie Matsliah
SIAM Journal on Computing, 2013
Active Property Testing
Maria-Florina Balcan, Eric Blais, Avrim Blum, and Liu Yang
FOCS 2012 | arXiv
Tight Bounds for Testing k-Linearity
Eric Blais and Daniel Kane
RANDOM 2012
Property Testing Lower Bounds via Communication Complexity
Eric Blais, Joshua Brody, and Kevin Matulef
Computational Complexity, 2012 | CCC 2011 | ECCC
k+ Decision Trees
James Aspnes, Eric Blais, Murat Demirbas, Ryan O’Donnell, Atri Rudra, and Steve Uurtamo
ALGOSENSORS 2010
Lower Bounds for Testing Function Isomorphism
Eric Blais and Ryan O’Donnell
CCC 2010
Polynomial Regression under Arbitrary Product Distributions
Eric Blais, Ryan O’Donnell, and Karl Wimmer
Machine Learning, 2010 | COLT 2008
Testing Juntas Nearly Optimally
Eric Blais
STOC 2009
Longest Common Subsequences in Sets of Permutations
Paul Beame, Eric Blais, and Dang-Trinh Huynh-Ngoc
arXiv
Improved Bounds for Testing Juntas
Eric Blais
RANDOM 2008
Gene Maps Linearization Using Genomic Rearrangement Distances
Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, and Nadia El-Mabrouk
Journal of Computational Biology, 2007 | RECOMB 2006
Common Substrings in Random Strings
Eric Blais and Mathieu Blanchette
CPM 2006
On the Inference of Parsimonious Indel Evolutionary Scenarios
Leonid Chindelevitch, Zhentao Li, Eric Blais, and Mathieu Blanchette
J. Bioinformatics and Comp. Bio., 2006