Kevin Matulef

Phone: +1 617-275-6958
Email: matulef AT gmail, or matulef AT mit

I am currently CTO at Calyx Health.

From 2014-2017 I was a senior member of the technical staff at Sandia National Labs in Livermore, California.

From 2013-2014, I was a postdoctoral researcher at Aarhus University as part of CTIC and MADALGO.

From 2011-2012, I was a member of the technical staff at MongoDB Inc.

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

I obtained my Ph.D. in 2009 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.

In a past life, I obtained a Master of Advanced Study in Mathematics from Cambridge University, and a Bachelor of Science from Brown University.

Publications:

• Property Testing on Linked Lists
  P. Afshani, K. Matulef, B. T. Wilkinson.
  Manuscript, 2013.
  

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

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.