Publications

Randomised Composition and Small-Bias Minimax
Shalev Ben-David, Eric Blais, Mika Goos, Gilbert Maystre
FOCS 2022.

PDF arXiv

VC Dimension and Distribution-Free Sample-Based Testing
Eric Blais, Renato Ferreira Pinto Jr., Nathan Harms
STOC 2021.

PDF DOI arXiv

Box Covers and Domain Orderings for Beyond Worst-Case Join Processing
Kaleb Alway, Eric Blais, Semih Salihoglu
ICDT 2021.

PDF DOI arXiv

A New Minimax Theorem for Randomized Algorithms
Shalev Ben-David, Eric Blais
FOCS 2020.

PDF DOI arXiv

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David, Eric Blais
FOCS 2020.

PDF DOI arXiv

On Testing and Robust Characterizations of Convexity
Eric Blais, Abhinav Bommireddi
RANDOM 2020.

PDF DOI

Testing Convexity of Functions over Finite Domains
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
SODA 2020.

PDF DOI arXiv

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
ACM Transactions on Computation Theory, 2019.

PDF DOI arXiv ECCC

Optimal Separation and Strong Direct Sum for Randomized Query Complexity
Eric Blais, Joshua Brody
CCC 2019.

PDF DOI Proceedings arXiv

Distribution Testing Lower Bounds via Reductions from Communication Complexity
Eric Blais, Clément L. Canonne, Tom Gur
ACM Transactions on Computation Theory, 2019.

PDF DOI ECCC

A Characterization of Constant-Sample Testable Properties
Eric Blais, Yuichi Yoshida
Random Structures & Algorithms, 2019.

PDF DOI arXiv ECCC

Testing Submodularity and Other Properties of Valuation Functions
Eric Blais, Abhinav Bommireddi
ITCS 2017.

PDF DOI arXiv

I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making
Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld
VLDB 2017.

PDF DOI

A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization
Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Peter van Beek
Canadian AI 2017.

PDF DOI

Testing Juntas and Related Properties of Boolean Functions
Eric Blais
Encyclopedia of Algorithms, 2016.

PDF DOI

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms
Ronitt Rubinfeld, Eric Blais
Handbook of Big Data, 2016.

PDF DOI

Learning and Testing Junta Distributions
Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld
COLT 2016.

PDF Proceedings

A Polynomial Lower Bound for Testing Monotonicity
Aleksandrs Belovs, Eric Blais
STOC 2016.

PDF DOI arXiv

A Mathematical Model of Performance-Relevant Feature Interactions
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Huiqun Yu
SPLC 2016.

PDF DOI

Rapid Sampling for Visualizations with Ordering Guarantees
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld
VLDB 2015.

PDF DOI arXiv

Quantum Algorithm for Monotonicity Testing on the Hypercube
Aleksandrs Belovs, Eric Blais
Theory of Computing, 2015.

PDF DOI arXiv

Performance Prediction of Configurable Software Systems by Fourier Learning
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki
ASE 2015.

PDF DOI

Partially Symmetric Functions Are Efficiently Isomorphism Testable
Eric Blais, Amit Weinstein, Yuichi Yoshida
SIAM Journal on Computing, 2015.

PDF DOI arXiv

Learning Circuits with Few Negations
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
RANDOM 2015.

PDF DOI arXiv ECCC

Approximating Boolean Functions with Depth-2 Circuits
Eric Blais, Li-Yang Tan
SIAM Journal on Computing, 2015.

PDF DOI ECCC

An Inequality for the Fourier Spectrum of Parity Decision Trees
Eric Blais, Li-Yang Tan, Andrew Wan
arXiv preprint, 2015.

PDF

The Information Complexity of Hamming Distance
Eric Blais, Joshua Brody, Badih Ghazi
RANDOM 2014.

PDF DOI Proceedings

Semi-Strong Colouring of Intersecting Hypergraphs
Eric Blais, Amit Weinstein, Yuichi Yoshida
Combinatorics, Probability, and Computing, 2014.

PDF DOI arXiv

On DNF Approximators for Monotone Boolean Functions
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
ICALP 2014.

PDF DOI

Lower Bounds for Testing Properties of Functions over Hypergrid Domains
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
CCC 2014.

PDF DOI ECCC

Nearly Tight Bounds for Testing Function Isomorphism
Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah
SIAM Journal on Computing, 2013.

PDF DOI

Hypercontractivity Via the Entropy Method
Eric Blais, Li-Yang Tan
Theory of Computing, 2013.

PDF DOI

Tight Bounds for Testing k-Linearity
Eric Blais, Daniel M. Kane
RANDOM 2012.

PDF DOI

Property Testing Lower Bounds via Communication Complexity
Eric Blais, Joshua Brody, Kevin Matulef
Computational Complexity, 2012.

PDF DOI ECCC

Active Property Testing
Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang
FOCS 2012.

PDF DOI arXiv

Testing Juntas: A Brief Survey
Eric Blais
Property Testing - Current Research and Surveys, 2010.

PDF DOI

Testing Boolean Function Isomorphism
Noga Alon, Eric Blais
RANDOM 2010.

PDF DOI

Polynomial Regression Under Arbitrary Product Distributions
Eric Blais, Ryan O'Donnell, Karl Wimmer
Machine Learning, 2010.

PDF DOI

Lower Bounds for Testing Function Isomorphism
Eric Blais, Ryan O'Donnell
CCC 2010.

PDF DOI

k+ Decision Trees
James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo
ALGOSENSORS 2010.

PDF DOI

Longest Common Subsequences in Sets of Permutations
Paul Beame, Eric Blais, Dang-Trinh Huynh-Ngoc
arXiv preprint, 2009.

PDF

Testing Juntas Nearly Optimally
Eric Blais
STOC 2009.

PDF DOI

Improved Bounds for Testing Juntas
Eric Blais
RANDOM 2008.

PDF DOI

Gene Maps Linearization Using Genomic Rearrangement Distances
Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk
Journal of Computational Biology, 2007.

DOI

On the Inference of Parsimonious Indel Evolutionary Scenarios
Leonid Chindelevitch, Zhentao Li, Eric Blais, Mathieu Blanchette
Journal of Bioinformatics and Computational Biology, 2006.

DOI

Common Substrings in Random Strings
Eric Blais, Mathieu Blanchette
CPM 2006.

DOI