Michael Dinitz

141 papers A* 32A 20B 7C 1Misc 1Journal 70Unranked 9

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More. SODA Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou
2026	J	`jnl`	Ski Rental with Distributional Predictions of Unknown Quality. CoRR Qiming Cui, Michael Dinitz
2025	J	`jnl`	A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances. CoRR Michael Dinitz, Chenglin Fan, Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou
2025	A*	`conf`	Almost Tight Bounds for Differentially Private Densest Subgraph. SODA Michael Dinitz, Satyen Kale, Silvio Lattanzi, Sergei Vassilvitskii
2025	A*	`conf`	Approximation Algorithms for Optimal Hopsets. ICALP Michael Dinitz, Ama Koranteng, Yasamin Nazari
2025	J	`jnl`	Approximation Algorithms for Optimal Hopsets. CoRR Michael Dinitz, Ama Koranteng, Yasamin Nazari
2025	B	`conf`	Controlling Tail Risk in Two-Slope Ski Rental. WAOA Qiming Cui, Michael Dinitz
2025	J	`jnl`	Controlling tail risk in two-slope ski rental. CoRR Qiming Cui, Michael Dinitz
2025	J	`jnl`	Differentially Private Matchings. CoRR Michael Dinitz, George Z. Li, Quanquan C. Liu, Felix Zhou
2025	J	`jnl`	Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines. CoRR Michael Dinitz, Jeremy T. Fineman, Seeun William Umboh
2025	A*	`conf`	Light Edge Fault Tolerant Graph Spanners. ICALP Greg Bodwin, Michael Dinitz, Ama Koranteng, Lily Wang
2025	J	`jnl`	Light Edge Fault Tolerant Graph Spanners. CoRR Greg Bodwin, Michael Dinitz, Ama Koranteng, Lily Wang
2025	J	`jnl`	Minimum Congestion Routing of Unsplittable Flows in Data-Center Networks. CoRR Miguel Alves Ferreira, Nirav Atre, Justine Sherry, Michael Dinitz, João L. Sobrinho
2024	A*	`conf`	Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks. INFOCOM Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, Long Luo, Stefan Schmid
2024	J	`jnl`	Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks. CoRR Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, Long Luo, Stefan Schmid
2024	A*	`conf`	Binary Search with Distributional Predictions. NeurIPS Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, Sergei Vassilvitskii
2024	J	`jnl`	Binary Search with Distributional Predictions. CoRR Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, Sergei Vassilvitskii
2024	A*	`conf`	Controlling Tail Risk in Online Ski-Rental. SODA Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2024	A	`conf`	Degrees and Network Design: New Problems and Approximations. APPROX/RANDOM Michael Dinitz, Guy Kortsarz, Shi Li
2024	J	`jnl`	Differentially Private Multiway and k-Cut. CoRR Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou
2024	J	`jnl`	Noise is All You Need: Private Second-Order Convergence of Noisy SGD. CoRR Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan, Grigory Yaroslavtsev
2024	A	`conf`	Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling. DISC Laxman Dhulipala, Michael Dinitz, Jakub Lacki, Slobodan Mitrovic
2024	J	`jnl`	Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling. CoRR Laxman Dhulipala, Michael Dinitz, Jakub Lacki, Slobodan Mitrovic
2024	J	`jnl`	Smoothed Analysis of Information Spreading in Dynamic Networks. J. ACM Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2023	J	`jnl`	Controlling Tail Risk in Online Ski-Rental. CoRR Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2023	J	`jnl`	Degrees and Network Design: New Problems and Approximations. CoRR Michael Dinitz, Guy Kortsarz, Shi Li
2023	A	`conf`	Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. ITCS Greg Bodwin, Michael Dinitz, Yasamin Nazari
2023	B	`conf`	Improved Approximations for Relative Survivable Network Design. WAOA Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov
2023	J	`jnl`	Improved Approximations for Relative Survivable Network Design. CoRR Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov
2023	J	`jnl`	Improved Differentially Private Densest Subgraph: Local and Purely Additive. CoRR Michael Dinitz, Satyen Kale, Silvio Lattanzi, Sergei Vassilvitskii
2022	A*	`conf`	Algorithms with Prediction Portfolios. NeurIPS Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2022	J	`jnl`	Algorithms with Prediction Portfolios. CoRR Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2022	A	`conf`	Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. DISC Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, Stefan Schmid
2022	A	`conf`	Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks. AISTATS Amy E. Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
2022	J	`jnl`	Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks. CoRR Amy Babay, Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
2022	J	`jnl`	Epic Fail: Emulators can tolerate polynomially many edge faults for free. CoRR Greg Bodwin, Michael Dinitz, Yasamin Nazari
2022	A	`conf`	Fair Disaster Containment via Graph-Cut Problems. AISTATS Michael Dinitz, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
2022	A*	`conf`	Partially Optimal Edge Fault-Tolerant Spanners. SODA Greg Bodwin, Michael Dinitz, Caleb Robelle
2022	A	`conf`	Relative Survivable Network Design. APPROX/RANDOM Michael Dinitz, Ama Koranteng, Guy Kortsarz
2022	J	`jnl`	Relative Survivable Network Design. CoRR Michael Dinitz, Ama Koranteng, Guy Kortsarz
2022	A	`conf`	Smoothed Analysis of Information Spreading in Dynamic Networks. DISC Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2022	J	`jnl`	Smoothed Analysis of Information Spreading in Dynamic Networks. CoRR Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2022	A	`conf`	Vertex Fault-Tolerant Emulators. ITCS Greg Bodwin, Michael Dinitz, Yasamin Nazari
2021	J	`jnl`	Fair Disaster Containment via Graph-Cut Problems. CoRR Amy Babay, Michael Dinitz, Prathyush Sambaturu, Aravind Srinivasan, Leonidas Tsepenekas, Anil Vullikanti
2021	A*	`conf`	Faster Matchings via Learned Duals. NeurIPS Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2021	J	`jnl`	Faster Matchings via Learned Duals. CoRR Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Sergei Vassilvitskii
2021	A*	`conf`	Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. SODA Greg Bodwin, Michael Dinitz, Caleb Robelle
2021	J	`jnl`	Partially Optimal Edge Fault-Tolerant Spanners. CoRR Greg Bodwin, Michael Dinitz, Caleb Robelle
2021	J	`jnl`	Vertex Fault-Tolerant Emulators. CoRR Greg Bodwin, Michael Dinitz, Yasamin Nazari
2020	J	`jnl`	Approximate Moore Graphs are good expanders. J. Comb. Theory B Michael Dinitz, Michael Schapira, Gal Shahaf
2020	J	`jnl`	Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. ACM Trans. Algorithms Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2020	J	`jnl`	Efficient and Simple Algorithms for Fault Tolerant Spanners. CoRR Michael Dinitz, Caleb Robelle
2020	A*	`conf`	Efficient and Simple Algorithms for Fault-Tolerant Spanners. PODC Michael Dinitz, Caleb Robelle
2020	B	`conf`	Lasserre Integrality Gaps for Graph Spanners and Related Problems. WAOA Michael Dinitz, Yasamin Nazari, Zeyu Zhang
2020	J	`jnl`	Optimal Vertex Fault-Tolerant Spanners in Polynomial Time. CoRR Greg Bodwin, Michael Dinitz, Caleb Robelle
2020	A*	`conf`	Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks. INFOCOM Michael Dinitz, Benjamin Moseley
2020	J	`jnl`	Scheduling for Weighted Flow and Completion Times in Reconfigurable Networks. CoRR Michael Dinitz, Benjamin Moseley
2019	—	`conf`	Approximating the Norms of Graph Spanners. APPROX-RANDOM Eden Chlamtác, Michael Dinitz, Thomas Robinson
2019	A	`conf`	Brief Announcement: Massively Parallel Approximate Distance Sketches. DISC Michael Dinitz, Yasamin Nazari
2019	A*	`conf`	Distributed Minimum Degree Spanning Trees. PODC Michael Dinitz, Magnús M. Halldórsson, Taisuke Izumi, Calvin Newport
2019	J	`jnl`	Lasserre Integrality Gaps for Graph Spanners and Related Problems. CoRR Michael Dinitz, Yasamin Nazari, Zeyu Zhang
2019	B	`conf`	Massively Parallel Approximate Distance Sketches. OPODIS Michael Dinitz, Yasamin Nazari
2019	C	`conf`	Reception Capacity: Definitions, Game Theory and Hardness. ALGOSENSORS Michael Dinitz, Naomi Ephraim
2019	A	`conf`	The Capacity of Smartphone Peer-To-Peer Networks. DISC Michael Dinitz, Magnús M. Halldórsson, Calvin Newport, Alex Weaver
2019	J	`jnl`	The Capacity of Smartphone Peer-to-Peer Networks. CoRR Michael Dinitz, Magnús M. Halldórsson, Calvin Newport, Alex Weaver
2019	A*	`conf`	The Norms of Graph Spanners. ICALP Eden Chlamtác, Michael Dinitz, Thomas Robinson
2019	J	`jnl`	The Norms of Graph Spanners. CoRR Eden Chlamtác, Michael Dinitz, Thomas Robinson
2018	A*	`conf`	Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. ICALP Amy Babay, Michael Dinitz, Zeyu Zhang
2018	—	`conf`	Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. FSTTCS Amy Babay, Michael Dinitz, Zeyu Zhang
2018	J	`jnl`	Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network. CoRR Amy Babay, Michael Dinitz, Zeyu Zhang
2018	J	`jnl`	Distributed Algorithms for Minimum Degree Spanning Trees. CoRR Michael Dinitz, Magnús M. Halldórsson, Calvin Newport
2018	J	`jnl`	Distributed Approximate Distance Oracles. CoRR Michael Dinitz, Yasamin Nazari
2018	A	`conf`	Large Low-Diameter Graphs are Good Expanders. ESA Michael Dinitz, Michael Schapira, Gal Shahaf
2018	A*	`conf`	Optimal Vertex Fault Tolerant Spanners (for fixed stretch). SODA Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams
2018	A*	`conf`	Policy Regret in Repeated Games. NeurIPS Raman Arora, Michael Dinitz, Teodor Vanislavov Marinov, Mehryar Mohri
2018	J	`jnl`	Policy Regret in Repeated Games. CoRR Raman Arora, Michael Dinitz, Teodor V. Marinov, Mehryar Mohri
2018	J	`jnl`	Smoothed analysis of dynamic networks. Distributed Comput. Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2018	J	`jnl`	The Densest k-Subhypergraph Problem. SIAM J. Discret. Math. Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2017	A	`conf`	Approximating Approximate Distance Oracles. ITCS Michael Dinitz, Zeyu Zhang
2017	A*	`conf`	Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. SODA Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2017	J	`jnl`	Approximating k-spanners in the LOCAL model. CoRR Michael Dinitz, Yasamin Nazari
2017	B	`conf`	Distributed Distance-Bounded Network Design Through Distributed Convex Programming. OPODIS Michael Dinitz, Yasamin Nazari
2017	J	`jnl`	Explicit Expanding Expanders. Algorithmica Michael Dinitz, Michael Schapira, Asaf Valadarsky
2017	J	`jnl`	Improved Approximation Algorithm for Steiner ACM Trans. Algorithms Michael Dinitz, Guy Kortsarz, Zeev Nutov
2017	A*	`conf`	Load balancing with bounded convergence in dynamic networks. INFOCOM Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2017	A*	`conf`	Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. SODA Eden Chlamtác, Michael Dinitz, Yury Makarychev
2017	J	`jnl`	Multicast Capacity Through Perfect Domination. CoRR Michael Dinitz, Naomi Ephraim
2017	J	`jnl`	Optimal Vertex Fault Tolerant Spanners (for fixed stretch). CoRR Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams
2017	A	`conf`	Timely, Reliable, and Cost-Effective Internet Transport Service Using Dissemination Graphs. ICDCS Amy Babay, Emily Wagner, Michael Dinitz, Yair Amir
2016	J	`jnl`	Approximating Approximate Distance Oracles. CoRR Michael Dinitz, Zeyu Zhang
2016	A*	`conf`	Approximating Low-Stretch Spanners. SODA Michael Dinitz, Zeyu Zhang
2016	J	`jnl`	Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds. CoRR Eden Chlamtác, Michael Dinitz, Guy Kortsarz, Bundit Laekhanukit
2016	—	`conf`	Computing Approximate PSD Factorizations. APPROX-RANDOM Amitabh Basu, Michael Dinitz, Xin Li
2016	J	`jnl`	Computing approximate PSD factorizations. CoRR Amitabh Basu, Michael Dinitz, Xin Li
2016	J	`jnl`	Label Cover Instances with Large Girth and the Hardness of Approximating Basic ACM Trans. Algorithms Michael Dinitz, Guy Kortsarz, Ran Raz
2016	J	`jnl`	Lowest-Degree k-Spanner: Approximation and Hardness. Theory Comput. Eden Chlamtác, Michael Dinitz
2016	J	`jnl`	Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion. CoRR Eden Chlamtác, Michael Dinitz, Yury Makarychev
2016	—	`conf`	The Densest k-Subhypergraph Problem. APPROX-RANDOM Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2016	J	`jnl`	The Densest k-Subhypergraph Problem. CoRR Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca
2016	A	`conf`	Xpander: Towards Optimal-Performance Datacenters. CoNEXT Asaf Valadarsky, Gal Shahaf, Michael Dinitz, Michael Schapira
2015	J	`jnl`	Efficient distributed computation of distance sketches in networks. Distributed Comput. Atish Das Sarma, Michael Dinitz, Gopal Pandurangan
2015	A	`conf`	Explicit Expanding Expanders. ESA Michael Dinitz, Michael Schapira, Asaf Valadarsky
2015	J	`jnl`	Explicit Expanding Expanders. CoRR Michael Dinitz, Michael Schapira, Asaf Valadarsky
2015	J	`jnl`	Introduction to the Special Issue on SPAA 2013. ACM Trans. Parallel Comput. Michael Dinitz, Torsten Hoefler
2015	A	`conf`	Smoothed Analysis of Dynamic Networks. DISC Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin C. Newport
2015	J	`jnl`	Smoothed Analysis of Dynamic Networks. CoRR Michael Dinitz, Jeremy T. Fineman, Seth Gilbert, Calvin Newport
2015	—	`conf`	Towards Resistance Sparsifiers. APPROX-RANDOM Michael Dinitz, Robert Krauthgamer, Tal Wagner
2015	J	`jnl`	Towards Resistance Sparsifiers. CoRR Michael Dinitz, Robert Krauthgamer, Tal Wagner
2015	Misc	`conf`	Xpander: Unveiling the Secrets of High-Performance Datacenters. HotNets Asaf Valadarsky, Michael Dinitz, Michael Schapira
2014	—	`conf`	Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights. APPROX-RANDOM Michael Dinitz, Guy Kortsarz, Zeev Nutov
2014	—	`conf`	Lowest Degree k-Spanner: Approximation and Hardness. APPROX-RANDOM Eden Chlamtác, Michael Dinitz
2014	J	`jnl`	Matroid Secretary for Regular and Decomposable Matroids. SIAM J. Comput. Michael Dinitz, Guy Kortsarz
2013	A	`conf`	Braess's Paradox in Wireless Networks: The Danger of Improved Technology. DISC Michael Dinitz, Merav Parter
2013	J	`jnl`	Braess's Paradox in Wireless Networks: The Danger of Improved Technology. CoRR Michael Dinitz, Merav Parter
2013	A*	`conf`	Matroid Secretary for Regular and Decomposable Matroids. SODA Michael Dinitz, Guy Kortsarz
2013	B	`conf`	Packing Interdiction and Partial Covering Problems. IPCO Michael Dinitz, Anupam Gupta
2013	J	`jnl`	Recent advances on the matroid secretary problem. SIGACT News Michael Dinitz
2012	B	`conf`	Efficient computation of distance sketches in distributed networks. SPAA Atish Das Sarma, Michael Dinitz, Gopal Pandurangan
2012	J	`jnl`	Everywhere-Sparse Spanners via Dense Subgraphs CoRR Eden Chlamtac, Michael Dinitz, Robert Krauthgamer
2012	A*	`conf`	Everywhere-Sparse Spanners via Dense Subgraphs. FOCS Eden Chlamtac, Michael Dinitz, Robert Krauthgamer
2012	—	`conf`	Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner. ICALP (1) Michael Dinitz, Guy Kortsarz, Ran Raz
2012	J	`jnl`	Label Cover instances with large girth and the hardness of approximating basic k-spanner CoRR Michael Dinitz, Guy Kortsarz, Ran Raz
2012	J	`jnl`	Matroid Secretary for Regular and Decomposable Matroids CoRR Michael Dinitz, Guy Kortsarz
2012	—	`conf`	iBGP and Constrained Connectivity. APPROX-RANDOM Michael Dinitz, Gordon T. Wilfong
2011	A*	`conf`	Directed spanners via flow-based linear programs. STOC Michael Dinitz, Robert Krauthgamer
2011	J	`jnl`	Efficient Computation of Distance Sketches in Distributed Networks CoRR Atish Das Sarma, Michael Dinitz, Gopal Pandurangan
2011	J	`jnl`	Fault-Tolerant Spanners: Better and Simpler CoRR Michael Dinitz, Robert Krauthgamer
2011	A*	`conf`	Fault-tolerant spanners: better and simpler. PODC Michael Dinitz, Robert Krauthgamer
2011	J	`jnl`	iBGP and Constrained Connectivity CoRR Michael Dinitz, Gordon T. Wilfong
2010	—	`—`	Algorithms and Models for Problems in Networking. Michael Dinitz
2010	J	`jnl`	Directed Spanners via Flow-Based Linear Programs CoRR Michael Dinitz, Robert Krauthgamer
2010	A*	`conf`	Distributed Algorithms for Approximating Wireless Network Capacity. INFOCOM Michael Dinitz
2010	J	`jnl`	Graphical representations of clutters. Ars Comb. Michael Dinitz, Jonah M. Gold, Thomas C. Sharkey, Lorenzo Traldi
2009	A*	`conf`	Brief announcement: distributed algorithms for approximating wireless network capacity. PODC Michael Dinitz
2009	A*	`conf`	Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory. INFOCOM Matthew Andrews, Michael Dinitz
2009	A*	`conf`	Secretary problems: weights and discounts. SODA Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar
2008	A*	`conf`	Online and dynamic embeddings of approximate ultrametrics. PODC Michael Dinitz
2008	A	`conf`	Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics. DISC Michael Dinitz
2007	A*	`conf`	Compact routing with slack. PODC Michael Dinitz
2006	J	`jnl`	Full Rank Tilings of Finite Abelian Groups. SIAM J. Discret. Math. Michael Dinitz
2006	A	`conf`	Spanners with Slack. ESA T.-H. Hubert Chan, Michael Dinitz, Anupam Gupta