Michael Dinitz
Graduate Student

Department of Computer Science
Carnegie Mellon University
4212 Wean Hall
Pittsburgh, PA 15213

mdinitz [at] cs [dot] cmu [dot] edu
Tel:(412) 268-7375
Office: Doherty 4301H

About Me

I am currently a third year graduate student in the Computer Science Department of the School of Computer Science at Carnegie Mellon University, where I am pursuing my doctorate under the supervision of Anupam Gupta. I am fortunate to be supported by an NSF Graduate Research Fellowship and an ARCS scholarship. Previously I was a student at Princeton University, where I majored in Computer Science and received a certificate in Applied and Computational Mathematics.  I grew up in Hinesburg, Vermont, graduating from Champlain Valley Union High School in 2001.  My parents both work at the University of Vermont -- my father, Jeffrey Dinitz, is a mathematician, and my mother, Susan Dinitz, is the director of the writing center.

Research Interests

I am generally interested in theoretical computer science, including algorithms, metric embeddings, complexity theory, graph theory, etc.  Most of my current work focuses on approximation algorithms, in which we attempt to design algorithms that, while not always returning the optimal solution, (provably) never do much worse than optimal.  I am also generally interested in any kind of math that comes up in the course of algorithms research, especially interesting graph theory and combinatorics.  

Publications

Secretary Problems: Weights and Discounts, with Moshe Babaioff, Anupam Gupta, Nicole Immorlica, and Kunal Talwar. Submitted.

Online and Dynamic Embeddings of Approximate Ultrametrics. Submitted.

Compact Routing with Slack. ACM Symposium on Principles of Distributed Computing (PODC) 2007. Slides

Spanners with Slack, with T-H. Hubert Chan and Anupam Gupta.  ESA 2006. Slides from CMU Theory Lunch.

Full rank tilings of finite abelian groups. SIAM Journal on Discrete Mathematics, 20 (2006), pp. 160-170

Graphical Representations of Clutters, with L. Traldi, J. Gold, and T. Sharkey. To appear in Ars Combinatoria

Enumeration of Balanced Tournament Designs on 10 points, with J. Dinitz. Journal of Combinatorial Mathematics and Combinatorial Computing, 52 (2005), 51 - 64.

Courses

I am currently taking Advanced Approximation Algorithms.
In the fall 0f 2007 I took Spectral Graph Theory and was a TA for Algorithms.
In the spring of 2007 I took Analysis of Boolean Functions, Computer Networks, and Planning Execution and Learning.
In the fall of 2006 I took Computational Complexity Theory and Advanced Computer Architecture.
In the spring of 2006 I took Approximation Algorithms II and Machine Learning Theory.
In the fall of 2005 I took Approximation Algorithms and Type Systems for Programming Languages.

Personal

When I'm not working, I enjoy fencing and alpine skiing.  I now fence (foil) at the CMU fencing club and occasionally at the Three Rivers Fencing Club.  I used to fence on the Princeton fencing team (go Tigers!), which was a great experience.  Unfortunately my extended stays in New Jersey and Pennsylvania have forced me to decrease the amount of skiing that I do, but I still try to make it back to Vermont a couple times a year.  When I do get the chance, I like to ski at Mad River Glen, a small area that's owned by a cooperative of skiers and has some of the best terrain in the east.