Eric Blais

Simons Postdoctoral Fellow, MIT

Stata Center 32-G666, 77 Vassar St., Cambridge, MA 02139
eb...@csail.mit.edu

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

*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

with N. Alon

*RANDOM '10*

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

*ALGOSENSORS '10*

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

*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*)

On the inference of parsimonious indel scenarios

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

*Journal of Bioinformatics and Computational Biology*, 2006

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

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

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

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

with N. Alon

Lower bounds for testing function isomorphism

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

arXiv Report 0904.1615

Testing juntas nearly optimally

Improved bounds for testing juntas

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,

On the inference of parsimonious indel scenarios

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

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

Ph.D. Thesis, Carnegie Mellon University, 2012

Testing juntas: a brief survey

Invited chapter in

Common substrings in random strings

Master's Thesis, McGill University, 2006

(Conference version with M. Blanchette,

Graphics processing method and system

with I. Ameline

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