Eric Blais

Carnegie Mellon University

Computer Science Dept.

5000 Forbes Avenue

Pittsburgh, PA 15213

Computer Science Dept.

5000 Forbes Avenue

Pittsburgh, PA 15213

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.

Publications

Semi-strong coloring of intersecting hypergraphs

with A. Weinstein and Y. Yoshida

*Manuscript*

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

*RANDOM '12*

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

*RANDOM '10*

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

*ALGOSENSORS '10*

Longest common subsequences in sets of permutations

with P. Beame and D.-T. Huynh-Ngoc

*Manuscript*

Testing juntas nearly optimally (pdf)

*STOC '09*

Improved bounds for testing juntas (pdf)

*RANDOM '08*

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

with A. Weinstein and Y. Yoshida

Partially symmetric functions are efficiently isomorphism-testable

with A. Weinstein and Y. Yoshida

Active property testing

with M.-F. Balcan, A. Blum, and L. Yang

Tight bounds for testing

with D. Kane

Property testing lower bounds via communication complexity

with J. Brody and K. Matulef

(Conference version in

Testing boolean function isomorphism (pdf)

with N. Alon

Lower bounds for testing function isomorphism (pdf)

with R. O'Donnell

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)

Improved bounds for testing juntas (pdf)

Polynomial regression under arbitrary product spaces

with R. O'Donnell and K. Wimmer

(Conference version,

Gene maps linearization using genomic rearrangement distances

with G. Blin, D. Hermelin, P. Guillon, M. Blanchette, and N. El-Mabrouk

(Conference version,

Common substrings in random strings

(Conference version with M. Blanchette,

On the inference of parsimonious indel scenarios

with L. Chindelevitch, Z. Li, and M. Blanchette

Graphics processing method and system

with I. Ameline

U.S. patent application 20060087518 (10/969,878), 2004

Teaching

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)

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)