Eric Blais
Simons Postdoctoral Fellow, MIT
Stata Center 32-G666, 77 Vassar St., Cambridge, MA 02139

As of August 2014, this page is no longer maintained. See here for my current page.

From 2012 to 2014, I was the Simons Postdoctoral Fellow with the Theory of Computation group of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. I completed my Ph.D. with Ryan O'Donnell at Carnegie Mellon University in 2012.

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
On DNF approximators for monotone Boolean functions
with J. Håstad, R. Servedio, and L.-Y. Tan
Manuscript, 2013.

Discrete isoperimetry via the entropy method
with L.-Y. Tan and A. Wan
Manuscript, 2013.

Learning circuits with few negations
with C. Canonne, I. Carboni Oliveira, R. Servedio, and L.-Y. Tan
Manuscript, 2013.

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

Lower bounds for testing properties of functions on hypergrid domains
with S. Raskhodnikova and G. Yaroslavtsev
ECCC Technical report TR13-036, 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.

Approximating boolean functions with depth-2 circuits
with L.-Y. Tan
CCC '13

Semi-strong coloring of intersecting hypergraphs
with A. Weinstein and Y. Yoshida
Combinatorics, Probability, and Computing, 2013.

Partially symmetric functions are efficiently isomorphism-testable
with A. Weinstein and Y. Yoshida
FOCS '12

Active property testing
with M.-F. Balcan, A. Blum, and L. Yang
FOCS '12

Tight bounds for testing k-linearity
with D. Kane

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

Testing boolean function isomorphism
with N. Alon

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

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

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

Testing juntas nearly optimally
STOC '09

Improved bounds for testing juntas

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

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, RECOMB Comparative Genomics '06)

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

Other Publications
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, 2011

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

Graphics processing method and system
with I. Ameline
U.S. patent application 20060087518 (10/969,878), 2004