Eric Blais
Gates-Hillman 7125
Carnegie Mellon University
Computer Science Dept.
5000 Forbes Avenue
Pittsburgh, PA 15213

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

I recently completed my Ph.D. at Carnegie Mellon University with Ryan O'Donnell.

My area of research is theoretical computer science. I am particularly interested in complexity theory, with an emphasis on property testing and the analysis of boolean functions.
Semi-strong coloring of intersecting hypergraphs
with A. Weinstein and Y. Yoshida

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 (pdf)
with N. Alon

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

k+ decision trees (pdf)
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

Testing juntas nearly optimally (pdf)
STOC '09

Improved bounds for testing juntas (pdf)

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)

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

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

Graphics processing method and system
with I. Ameline
U.S. patent application 20060087518 (10/969,878), 2004
I was a teaching assistant for the following classes:

Intensive Introduction to Computational Complexity Theory
V. Guruswami and R. O'Donnell (Spring 2009)

Probability and Computing
M. Harchol-Balter and R. O'Donnell (Fall 2008)

Algorithms for Mining Biological Sequences
M. Blanchette (Spring 2006)

Algorithms and Data Structures
C. Crépeau (Spring 2005)

Introduction to Computer Science
M. Blanchette (Fall 2004, 2005)