Kevin Matulef

Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
32 Vassar Street, Bldg. 32-G608
Cambridge, MA 02139

Phone: (617) 275-6958, (617) 225-6306
Email: matulef AT mit DOT edu

I am currently a postdoc at Aarhus University as part of CTIC.

From 2011-2012 I was a member of the technical staff at 10gen working on MongoDB.

From 2009-2011 I was a postdoctoral researcher at ITCS, part of the IIIS at Tsinghua University in Beijing.

In 2009 I obtained my Ph.D. from the Department of Mathematics at MIT, where I was also a member of the Theory of Computation group in CSAIL. While in graduate school I frequently visited the Columbia University CS department.

I obtained a Certificate of Advanced Study in Mathematics from Cambridge University, and a Bachelor of Science from Brown University.

Publications:

• Lower Bounds for Testing Computability by Small Width OBDDs
  J. Brody, K. Matulef, C. Wu.
  8th Annual Theory and Applications of Models of Computation (TAMC), 2011.
        pdf (full version)

• Property Testing Lower Bounds via Communication Complexity
  E. Blais, J. Brody, K. Matulef.
  26th Conference on Computational Complexity (CCC), 2011.
        pdf (extended abstract)
        pdf (full version)

• Testing {-1,1}-Weight Halfspaces
  K. Matulef, R. O'Donnell, R. Rubinfeld , R. Servedio.
  13th International Workshop on Randomization and Computation (RANDOM), 2009.
        pdf, ps (full version)

• Testing Halfspaces
  K. Matulef, R. O'Donnell, R. Rubinfeld , R. Servedio.
  20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
        pdf, ps (extended abstract)
        pdf, ps (full version)

• Efficiently Testing Sparse GF(2) Polynomials
  I. Diakonikolas, H. Lee, K. Matulef, R. Servedio, A. Wan.
  35th International Colloquium on Automata, Languages and Programming (ICALP), 2008.
        pdf, ps (extended abstract, with full proofs in appendices)

• Testing For Concise Representations
  I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld , R. Servedio, A. Wan.
  48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.
        pdf, ps (extended abstract)
        pdf, ps (full version)

• Testing k-wise and Almost k-wise Independence
  N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, N. Xie.
  39th ACM Symposium on Theory of Computing (STOC), 2007.
        pdf, ps (extended abstract)

Professional:

CV

Teaching:

Spring 2013: Sublinear Time Algorithms: Property Testing at Aarhus, co-taught with Joshua Brody.

Fall 2010: Theoretical Computer Science II at Tsinghua.

Spring 2010: Property Testing and Fourier Analysis at Tsinghua, mini-course co-taught with Victor Chen

Fall 2008: TA for 6.046/18.410 Design and Analysis of Algorithms at MIT. My recitation notes can be found in the "materials" section of the stellar site.

Fall 2004 and Fall 2005: TA for 18.404/6.840 at MIT, Introduction to Theory of Computation.
My recitation notes can be found here.

Facebook Enemies:

Enemybook is a program that I wrote to remedy the one-sided perspective of Facebook.
It was featured in several media outlets including the Boston Globe (article) and NPR (interview1, interview2). More info on Enemybook can be found here.