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 Ph.D. student in the Department of Mathematics at MIT, and a member of the Theory of Computation group in CSAIL. I am also a frequent visitor to the Columbia University CS department. I expect to graduate at the end of this academic year.

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

Publications:

• Testing {-1,1}-Weight Halfspaces
  K. Matulef, R. O'Donnell, R. Rubinfeld , R. Servedio.
  To appear in the 13th International Workshop on Randomization and Computation (RANDOM), 2009.

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

In Fall 2008 I was a TA for for 6.046/18.410 Design and Analysis of Algorithms. My recitation notes can be found in the "materials" section of the stellar site.

In Fall 2004 and Fall 2005 I was a TA for 18.404/6.840, 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.