Dinitz, Michael

Assistant Professor
Computer Science
https://www.cs.jhu.edu/~mdinitz/

Malone 217
(410) 516-7185
mdinitz1@jhu.edu

Jump to:

About

Education
  • Ph.D. 2010, CARNEGIE MELLON UNIVERSITY
Research Areas
  • APPROXIMATION algorithms
  • Algorithms
  • Theoretical Computer Science
Presentations
  • "Approximating Low-Stretch Spanners and Distance Oracles", Workshop on Flexible Network Design.  Amsterdam, Netherlands.  July 6, 2016
  • "Approximating Spanners", Joint STOC-SoCG Workshop on Spanners: Graphs and Geometry.  Cambridge, MA.  June 18, 2016
  • "Towards Resistance Sparsifiers", Sublinear Algorithms Workshop.  Baltimore, MD.  January 8, 2016
  • "Packing Interdiction and Partial Covering Problems", International Symposium on Mathematical Programming.  Pittsburgh, PA.  July 13, 2015
  • "Approximating Graph Spanners", Theory Seminar.  Jerusalem, Israel.  June 24, 2015
  • "Smoothed Analysis of Dynamic Networks", Foundations of Computer Science Seminar.  Rehovot, Israel.  June 22, 2015
  • "Smoothed Analysis of Dynamic Networks", Networking Summer Workshop.  Jerusalem, Israel.  June 16, 2015
  • "Explicit Expanding Expanders", Maryland Theory Day.  College Park, MD.  October 10, 2014
  • "Approximating Graph Spanners", Workshop on Flexible Network Design.  Lugano, Switzerland.  July 31, 2014
  • "Label Cover Instances with Large Girth and the Hardness of Approximating Spanners", Capital Area Theory Seminar.  College Park, MD.  May 18, 2014
  • "Matroid Secretary for Regular and Decomposable Matroids", University of Pennsylvania Theory Seminar.  Philadelphia, PA.  March 8, 2014
  • "Braess's Paradox in Wireless Networks: The Danger of Improved Technology", Algorithms for Wireless Communication.  Wadern, Germany.  January 29, 2014

Publications

Journal Articles
  • Dinitz M, Schapira M, Shahaf G (2018).  Large low-diameter graphs are good expanders.  Leibniz International Proceedings in Informatics, LIPIcs.  112.
  • Dinitz M, Fineman JT, Gilbert S, Newport C (2018).  Smoothed analysis of dynamic networks.  Distributed Computing.  31(4).
  • Babay A, Dinitz M, Zhang Z (2018).  Brief announcement: Characterizing demand graphs for (fixed-parameter) shallow-light steiner network.  Leibniz International Proceedings in Informatics, LIPIcs.  107.
  • Dinitz M, Nazari Y (2018).  Distributed distance-bounded network design through distributed convex programming.  Leibniz International Proceedings in Informatics, LIPIcs.  95.
  • Bodwin G, Dinitz M, Parter M, Williams VV (2018).  Optimal vertex fault tolerant spanners (for fixed stretch).  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
  • Chlamtác E, Dinitz M, Konrad C, Kortsarz G, Rabanca G (2018).  The densest k-subhypergraph problem.  SIAM Journal on Discrete Mathematics.  32(2).
  • Dinitz M, Zhang Z (2017).  Approximating approximate distance oracles.  Leibniz International Proceedings in Informatics, LIPIcs.  67.
  • Dinitz M, Fineman J, Gilbert S, Newport C (2017).  Load balancing with bounded convergence in dynamic networks.  Proceedings - IEEE INFOCOM.
  • Dinitz M, Schapira M, Valadarsky A (2017).  Explicit Expanding Expanders.  Algorithmica.  78(4).
  • Babay A, Wagner E, Dinitz M, Amir Y (2017).  Timely, Reliable, and Cost-Effective Internet Transport Service Using Dissemination Graphs.  Proceedings - International Conference on Distributed Computing Systems.
  • Dinitz M, Kortsarz G, Nutov Z (2017).  Improved approximation algorithm for steiner k-forest with nearly uniform weights.  ACM Transactions on Algorithms.  13(3).
  • Chlamtác E, Dinitz M, Kortsarz G, Laekhanukitx B (2017).  Approximating spanners and directed steiner forest: Upper and lower bounds.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
  • Chlamtác E, Dinitz M, Makarychev Y (2017).  Minimizing the union: Tight approximations for small set bipartite vertex expansion.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
  • Valadarsky A, Shahaf G, Dinitz M, Schapira M (2016).  Xpander: Towards optimal-performance datacenters.  CoNEXT 2016 - Proceedings of the 12th International Conference on Emerging Networking EXperiments and Technologies.
  • Chlamtác E, Dinitz M, Konrad C, Kortsarz G, Rabanca G (2016).  The densest κ-subhypergraph problem.  Leibniz International Proceedings in Informatics, LIPIcs.  60.
  • Basu A, Dinitz M, Li X (2016).  Computing approximate PSD factorizations.  Leibniz International Proceedings in Informatics, LIPIcs.  60.
  • Dinitz M, Kortsarz G, Raz R (2016).  Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.  ACM Trans. Algorithms.  12(2).  25:1-25:16.
  • Chlamtác E, Dinitz M (2016).  Lowest-degree k-spanner: Approximation and hardness.  Theory of Computing.  12.
  • Dinitz M, Zhang Z (2016).  Approximating low-stretch spanners.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.  2.
  • Chlamtác E, Dinitz M (2016).  Lowest-Degree k-Spanner: Approximation and Hardness.  Theory of Computing.  12(1).  1-29.
  • Dinitz M, Kortsarz G, Raz R (2015).  Label cover instances with large girth and the hardness of approximating basic k-Spanner.  ACM Transactions on Algorithms.  12(2).
  • Valadarsky A, Dinitz M, Schapira M (2015).  Xpander: Unveiling the secrets of high-performance datacenters.  Proceedings of the 14th ACM Workshop on Hot Topics in Networks, HotNets-XIV 2015.
  • Sarma AD, Dinitz M, Pandurangan G (2015).  Efficient distributed computation of distance sketches in networks.  Distributed Computing.  28(5).
  • Dinitz M, Krauthgamer R, Wagner T (2015).  Towards resistance sparsifiers.  Leibniz International Proceedings in Informatics, LIPIcs.  40.
  • Sarma AD, Dinitz M, Pandurangan G (2015).  Efficient distributed computation of distance sketches in networks.  Distributed Computing.  28(5).  309-320.
  • Dinitz M, Hoefler T (2015).  Introduction to the special issue on SPAA 2013.  ACM Transactions on Parallel Computing.  2(3).
  • Dinitz M, Fineman J, Gilbert S, Newport C (2015).  Smoothed analysis of dynamic networks.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  9363.
  • Dinitz M, Schapira M, Valadarsky A (2015).  Explicit expanding expanders.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  9294.
  • Dinitz M, Kortsarz G, Nutov Z (2014).  Improved approximation algorithm for steiner κ-Forest with nearly uniform weights.  Leibniz International Proceedings in Informatics, LIPIcs.  28.
  • Dinitz M, Kortsarz G (2014).  Matroid Secretary for Regular and Decomposable Matroids.  SIAM J. Comput..  43(5).  1807-1830.
  • Chlamtác E, Dinitz M (2014).  Lowest degree κ-Spanner: Approximation and hardness.  Leibniz International Proceedings in Informatics, LIPIcs.  28.
  • Dinitz M, Kortsarz G (2014).  Matroid secretary for regular and decomposable matroids.  SIAM Journal on Computing.  43(5).
  • Dinitz M, Parter M (2013).  Braess's Paradox in wireless networks: The danger of improved technology.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  8205 LNCS.
  • Dinitz M, Kortsarz G (2013).  Matroid secretary for regular and decomposable matroids.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
  • Dinitz M, Gupta A (2013).  Packing interdiction and partial covering problems.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7801 LNCS.
  • Dinitz M (2013).  Recent advances on the matroid secretary problem.  SIGACT News.  44(2).  126-142.
  • Dinitz M, Kortsarz G, Raz R (2012).  Label cover instances with large girth and the hardness of approximating basic k-spanner.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7391 LNCS(PART 1).
  • Chlamtác E, Dinitz M, Krauthgamer R (2012).  Everywhere-sparse spanners via dense subgraphs.  Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS.
  • Dinitz M, Wilfong G (2012).  IBGP and constrained connectivity.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  7408 LNCS.
  • Sarma AD, Dinitz M, Pandurangan G (2012).  Efficient computation of distance sketches in distributed networks.  Annual ACM Symposium on Parallelism in Algorithms and Architectures.
  • Dinitz M, Krauthgamer R (2011).  Fault-tolerant spanners: Better and simpler.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing.
  • Dinitz M, Krauthgamer R (2011).  Directed spanners via flow-based linear programs.  Proceedings of the Annual ACM Symposium on Theory of Computing.
  • Dinitz M (2010).  Distributed algorithms for approximating wireless network capacity.  Proceedings - IEEE INFOCOM.
  • Dinitz M, Gold JM, Sharkey TC, Traldi L (2010).  Graphical representations of clutters.  Ars Comb..  94.
  • Dinitz M (2009).  Brief announcement: Distributed algorithms for approximating wireless network capacity.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing.
  • Dinitz M (2009).  Labels, routing, and capacity: Bringing theoretical networking closer to practice.  Proceedings - IEEE INFOCOM.
  • Andrews M, Dinitz M (2009).  Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory.  Proceedings - IEEE INFOCOM.
  • Babaioff M, Dinitz M, Gupta A, Immorlica N, Talwar K (2009).  Secretary problems: Weights and discounts.  Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
  • Dinitz M (2008).  Brief announcement: Online and dynamic embeddings of approximate ultrametrics.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing.
  • Dinitz M (2008).  Online, dynamic, and distributed embeddings of approximate ultrametrics.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  5218 LNCS.
  • Dinitz M (2007).  Compact routing with slack.  Proceedings of the Annual ACM Symposium on Principles of Distributed Computing.
  • Dinitz M (2006).  Full rank tilings of finite abelian groups.  SIAM Journal on Discrete Mathematics.  20(1).
  • Chan THH, Dinitz M, Gupta A (2006).  Spanners with slack.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).  4168 LNCS.
  • Dinitz M (2006).  Full Rank Tilings of Finite Abelian Groups.  SIAM J. Discrete Math..  20(1).  160-170.
  • Dinitz JH, Dinitz M (2005).  Enumeration of balanced tournament designs on 10 points.  J. Combin. Math. Combin. Comput..  52.  51-63.
Conference Proceedings
  • Dinitz MH, Nazari Y (2017).  Distributed Distance-Bounded Network Design Through Distributed Convex Programming.  The 21st International Conference on Principles of Distributed Systems.
  • Chlamtác E, Dinitz M, Kortsarz G, Laekhanukit B (2017).  Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds.  Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19.  SIAM.  534-553.
  • Chlamtác E, Dinitz M, Makarychev Y (2017).  Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion.  Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19.  SIAM.  881-899.
  • Valadarsky A, Shahaf G, Dinitz M, Schapira M (2016).  Xpander: Towards Optimal-Performance Datacenters.  Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies, CoNEXT 2016, Irvine, California, USA, December 12-15, 2016.  ACM.  205-219.
  • Dinitz M, Zhang Z (2016).  Approximating Low-Stretch Spanners.  Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016.  SIAM.  821-840.
  • Basu A, Dinitz M, Li X (2016).  Computing Approximate PSD Factorizations.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.  60.  2:1-2:12.
  • Chlamtác E, Dinitz M, Konrad C, Kortsarz G, Rabanca G (2016).  The Densest k-Subhypergraph Problem.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.  60.  6:1-6:19.
  • Valadarsky A, Dinitz M, Schapira M (2015).  Xpander: Unveiling the Secrets of High-Performance Datacenters.  Proceedings of the 14th ACM Workshop on Hot Topics in Networks, Philadelphia, PA, USA, November 16 - 17, 2015.  ACM.  16:1-16:7.
  • Dinitz M, Schapira M, Valadarsky A (2015).  Explicit Expanding Expanders.  Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings.  Springer.  9294.  399-410.
  • Dinitz M, Krauthgamer R, Wagner T (2015).  Towards Resistance Sparsifiers.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.  40.  738-755.
  • Dinitz M, Fineman JT, Gilbert S, Newport CC (2015).  Smoothed Analysis of Dynamic Networks.  Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings.  Springer.  9363.  513-527.
  • Dinitz M, Kortsarz G, Nutov Z (2014).  Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.  28.  115-127.
  • Chlamtác E, Dinitz M (2014).  Lowest Degree k-Spanner: Approximation and Hardness.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.  28.  80-95.
  • Dinitz M, Kortsarz G (2013).  Matroid Secretary for Regular and Decomposable Matroids.  Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013.  SIAM.  108-117.
  • Dinitz M, Gupta A (2013).  Packing Interdiction and Partial Covering Problems.  Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013..  Springer.  7801.  157-168.
  • Dinitz M, Parter M (2013).  Braess's Paradox in Wireless Networks: The Danger of Improved Technology.  Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings.  Springer.  8205.  477-491.
  • Dinitz M, Kortsarz G, Raz R (2012).  Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner.  Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I.  Springer.  7391.  290-301.
  • Chlamtac E, Dinitz M, Krauthgamer R (2012).  Everywhere-Sparse Spanners via Dense Subgraphs.  53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012.  IEEE Computer Society.  758-767.
  • Sarma AD, Dinitz M, Pandurangan G (2012).  Efficient computation of distance sketches in distributed networks.  24th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, Pittsburgh, PA, USA, June 25-27, 2012.  ACM.  318-326.
  • Dinitz M, Wilfong GT (2012).  iBGP and Constrained Connectivity.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings.  Springer.  7408.  122-133.
  • Dinitz M, Krauthgamer R (2011).  Fault-tolerant spanners: better and simpler.  Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, San Jose, CA, USA, June 6-8, 2011.  ACM.  169-178.
  • Dinitz M (2010).  Distributed Algorithms for Approximating Wireless Network Capacity.  INFOCOM 2010. 29th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 15-19 March 2010, San Diego, CA, USA.  IEEE.  1397-1405.
  • Andrews M, Dinitz M (2009).  Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory.  INFOCOM 2009. 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 19-25 April 2009, Rio de Janeiro, Brazil.  IEEE.  1332-1340.
  • Babaioff M, Dinitz M, Gupta A, Immorlica N, Talwar K (2009).  Secretary problems: weights and discounts.  Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009.  SIAM.  1245-1254.
  • Dinitz M (2008).  Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics.  Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings.  Springer.  5218.  152-166.
  • Dinitz M (2007).  Compact routing with slack.  Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007.  ACM.  81-88.
  • Chan HT, Dinitz M, Gupta A (2006).  Spanners with Slack.  Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings.  Springer.  4168.  196-207.
Back to top