Michael Dinitz
Graduate Student

Computer Science Department
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213

mdinitz [at] cs [dot] cmu [dot] edu
Tel:(412) 268-7375
Office: Gates-Hillman 7515

About Me

I am currently a fifth 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

Distributed Algorithms for Approximating Wireless Network Capacity. To appear at INFOCOM 2010

Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory, with Matthew Andrews. INFOCOM 2009.

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

Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics. DISC 2008.

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

In the spring of 2009 I was a TA for Graduate Algorithms.
In the spring of 2008 I took 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.