Michael Dinitz

NeurIPS Conference 2025 Conference Paper

A Generalized Binary Tree Mechanism for Private Approximation of All-Pair Shortest Distances

• Zongrui Zou
• Chenglin Fan
• Michael Dinitz
• Jingcheng Liu
• Jalaj Upadhyay

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as *recursively separable*. In particular, for any $n$-vertex $K_h$-minor-free graph, our algorithm achieve an additive error of $ \widetilde{O}(h(nW)^{1/3} ) $, where $ W $ represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of $ \widetilde{O}(n^{1/4}\sqrt{W}) $. Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are *recursively separable*.

SODA Conference 2025 Conference Paper

Almost Tight Bounds for Differentially Private Densest Subgraph

• Michael Dinitz
• Satyen Kale
• Silvio Lattanzi
• Sergei Vassilvitskii

We study the Densest Subgraph (DSG) problem under the additional constraint of differential privacy. DSG is a fundamental theoretical question that plays a central role in graph analytics, and so privacy is a natural requirement. All known private algorithms for Densest Subgraph lose constant multiplicative factors, despite the existence of non-private exact algorithms. We show that, perhaps surprisingly, this loss is not necessary: in both the classic differential privacy model and the LEDP model (local edge differential privacy, introduced recently by Dhulipala et al. [FOCS 2022]), we give ( ϵ, δ)-differentially private algorithms with no multiplicative loss whatsoever. In other words, the loss is purely additive. Moreover, our additive losses match or improve the previous state of the art additive loss (in any version of differential privacy) when 1/ δ is polynomial in n, and are almost tight: in the centralized setting, our additive loss is O (log n / ϵ ) while there is a known lower bound of. We also give a number of extensions. First, we show how to extend our techniques to both the node-weighted and the directed versions of the problem. Second, we give a separate algorithm with pure differential privacy (as opposed to approximate DP) but with worse approximation bounds. And third, we give a new algorithm for privately computing the optimal density which implies a separation between the structural problem of privately computing the densest subgraph and the numeric problem of privately computing the density of the densest subgraph.

NeurIPS Conference 2024 Conference Paper

Binary Search with Distributional Predictions

• Michael Dinitz
• Sungjin Im
• Thomas Lavastida
• Benjamin Moseley
• Aidin Niaparast
• Sergei Vassilvitskii

Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a *distribution*. We initiate the study of algorithms with *distributional* predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first *distributionally-robust* algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.

SODA Conference 2024 Conference Paper

Controlling Tail Risk in Online Ski-Rental

• Michael Dinitz
• Sungjin Im
• Thomas Lavastida
• Benjamin Moseley
• Sergei Vassilvitskii

The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is e / e -1-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large variance in its performance: it has more than a 37% chance of competitive ratio exceeding 2, and the change of the competitive ratio exceeding n is Θ(1/ n )! We ask what happens to the optimal solution if we insist that the tail risk, i. e. , the chance of the competitive ratio exceeding a specific value, is bounded by some constant δ. We find that this additional modification significantly changes the structure of the optimal solution. The probability of purchasing skis on a given day becomes non-monotone, discontinuous, and arbitrarily large (for sufficiently small tail risk δ and large purchase cost n ). * A full version of the paper can be accessed at https: //arxiv. org/abs/2308. 05067

NeurIPS Conference 2022 Conference Paper

Algorithms with Prediction Portfolios

• Michael Dinitz
• Sungjin Im
• Thomas Lavastida
• Benjamin Moseley
• Sergei Vassilvitskii

The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are not. Most previous work has assumed that the algorithm has access to a single predictor. However, in practice, there are many machine learning methods available, often with incomparable generalization guarantees, making it hard to pick a best method a priori. In this work we consider scenarios where multiple predictors are available to the algorithm and the question is how to best utilize them. Ideally, we would like the algorithm's performance to depend on the quality of the {\em best} predictor. However, utilizing more predictions comes with a cost, since we now have to identify which prediction is best. We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling, which have been well-studied in the single predictor setting. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.

SODA Conference 2022 Conference Paper

Partially Optimal Edge Fault-Tolerant Spanners

• Greg Bodwin
• Michael Dinitz
• Caleb Robelle

NeurIPS Conference 2021 Conference Paper

Faster Matchings via Learned Duals

• Michael Dinitz
• Sungjin Im
• Thomas Lavastida
• Benjamin Moseley
• Sergei Vassilvitskii

A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algorithmic insights into problems, with particular success in the design of competitive online algorithms. However, the question of improving algorithm running times with predictions has largely been unexplored. We take a first step in this direction by combining the idea of machine-learned predictions with the idea of ``warm-starting" primal-dual algorithms. We consider one of the most important primitives in combinatorial optimization: weighted bipartite matching and its generalization to $b$-matching. We identify three key challenges when using learned dual variables in a primal-dual algorithm. First, predicted duals may be infeasible, so we give an algorithm that efficiently maps predicted infeasible duals to nearby feasible solutions. Second, once the duals are feasible, they may not be optimal, so we show that they can be used to quickly find an optimal solution. Finally, such predictions are useful only if they can be learned, so we show that the problem of learning duals for matching has low sample complexity. We validate our theoretical findings through experiments on both real and synthetic data. As a result we give a rigorous, practical, and empirically effective method to compute bipartite matchings.

SODA Conference 2021 Conference Paper

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

• Greg Bodwin
• Michael Dinitz
• Caleb Robelle

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer k, every n -node graph has a (2 k – 1)-spanner on O ( f 1–1/ k n 1+1/ k ) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes Õ ( f 1–1/ k n 2+1/k + mf 2 ) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.

SODA Conference 2018 Conference Paper

Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

• Greg Bodwin
• Michael Dinitz
• Merav Parter
• Virginia Vassilevska Williams

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant ( VFT ) k -spanner if H \ F is a k -spanner of G \ F for any small set F of f vertices that might “fail. ” One of the main questions in the area is: what is the minimum size of an f fault tolerant k -spanner that holds for all n node graphs (as a function of f, k and n )? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n -node graph G has a (2 k – 1)- spanner resilient to f vertex faults with O k ( f 1–1/k n 1+1/ k ) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating dist G\F ( s, t ) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D( f 1/2-1/(2 k ) · n 1+1/ k ) for k > 3. We leave it as an open problem to close this gap.

NeurIPS Conference 2018 Conference Paper

Policy Regret in Repeated Games

• Raman Arora
• Michael Dinitz
• Teodor Vanislavov Marinov
• Mehryar Mohri

The notion of policy regret'' in online learning is supposed to capture the reactions of the adversary to the actions taken by the learner, which more traditional notions such as external regret do not take into account. We revisit this notion of policy regret, and first show that there are online learning settings in which policy regret and external regret are incompatible: any sequence of play which does well with respect to one must do poorly with respect to the other. We then focus on the game theoretic setting, when the adversary is a self-interested agent. In this setting we show that the external regret and policy regret are not in conflict, and in fact that a wide class of algorithms can ensure both as long as the adversary is also using such an algorithm. We also define a new notion of equilibrium which we call a policy equilibrium'', and show that no-policy regret algorithms will have play which converges to such an equilibrium. Relating this back to external regret, we show that coarse correlated equilibria (which no-external regret players will converge to) are a strict subset of policy equilibria. So in game-theoretic settings every sequence of play with no external regret also has no policy regret, but the converse is not true.

SODA Conference 2017 Conference Paper

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

• Eden Chlamtac
• Michael Dinitz
• Guy Kortsarz
• Bundit Laekhanukit

It was recently found that there are very close connectionsbetween the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA ‘16, Bodwin-Williams SODA ‘16]. We study these problemsfrom an optimization point of view, where ratherthan studying the existence of extremal instances we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5+∊ )-approximation for distance preservers and pairwisespanners (for arbitrary constant ∊ > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5+∊ )- approximation for the Directed Steiner Forest problem (for arbitrary constant ∊ > 0) when all edges have uniform costs, improving the previous best O ( n 2/3+∊ )- approximation due to Berman et al. [ICALP ‘11] (whichholds for general edge costs).

SODA Conference 2017 Conference Paper

Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion

• Eden Chlamtac
• Michael Dinitz
• Yury Makarychev

In the Minimum k -Union problem (M k U) we are given a set system with n sets and are asked to select k sets in order to minimize the size of their union. Despite being a very natural problem, it has received surprisingly little attention: the only known approximation algorithm is an due to [Chlamtac et al APPROX’16]. This problem can also be viewed as the bipartite version of the Small Set Vertex Expansion problem (SSVE), which we call the Small Set Bipartite Vertex Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes to minimize their vertex expansion, has not been as well studied as its edge-based counterpart Small Set Expansion (SSE), but has recently received significant attention, e. g. [Louis-Makarychev APPROX ‘15]. However, due to the connection to Unique Games and hardness of approximation the focus has mostly been on sets of size k = Ω( n ), while we focus on the case of general k, for which no polylogarithmic approximation is known. We improve the upper bound for this problem by giving an η 1/4 + ∊ approximation for SSBVE for any constant ∊ > 0. Our algorithm follows in the footsteps of Densest k -Subgraph (DkS) and related problems, by designing a tight algorithm for random models, and then extending it to give the same guarantee for arbitrary instances. Moreover, we show that this is tight under plausible complexity conjectures: it cannot be approximated better than O ( n 1/4 ) assuming an extension of the so-called “Dense versus Random” conjecture for DkS to hypergraphs. In addition to conjectured hardness via our reduction, we show that the same lower bound is also matched by an integrality gap for a super-constant number of rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for the natural SDP relaxation. Finally, we note that there exists a simple bicriteria approximation for the more general SSVE problem (where no non-trivial approximations were known for general k ).

SODA Conference 2016 Conference Paper

Approximating Low-Stretch Spanners

• Michael Dinitz
• Zeyu Zhang 0003

Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating basic k -spanner (particularly for small k ), and the dependence on f when approximating f -fault tolerant spanners. We first design an Õ ( n 1/3 )-approximation for 4-spanner (both basic and directed). This was the last value of k for which only an -approximation was known for basic k -spanner, and thus implies that for any k the approximation ratio is at most Õ ( n 1/3 ). For basic k -spanner, we also show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial approximation of. For f -fault tolerant spanners, we show that in the small-stretch setting (k ∊ {3, 4}) it is possible to entirely remove the dependence on f from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on f was either almost-linear (in the undirected setting) or exponential (in the directed setting for stretch 4).

SODA Conference 2013 Conference Paper

Matroid Secretary for Regular and Decomposable Matroids

• Michael Dinitz
• Guy Kortsarz

FOCS Conference 2012 Conference Paper

Everywhere-Sparse Spanners via Dense Subgraphs

• Eden Chlamtac
• Michael Dinitz
• Robert Krauthgamer

The significant progressg in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped spanners that are everywhere-sparse (small maximum degree). This disparity is in line with other network design problems, where the maximum-degree objective has been a notorious technical challenge. Our main result is for the Lowest Degree $2$-Spanner (LD2S) problem, where the goal is to compute a 2-spanner of an input graph so as to minimize the maximum degree. We design a polynomial-time algorithm achieving approximation factor O(\Delta^{3-2\sqrt{2}}) \approx O(\Delta^{0. 172}), where \Delta is the maximum degree of the input graph. The previous O(\Delta^{1/4}) -- approximation was proved nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998]. Our main conceptual contribution is to establish a formal connection between LD2S and a variant of the Densest k-Sub graph (DkS) problem. Specifically, we design for both problems strong relaxations based on the Sherali-Adams linear programming (LP) hierarchy, and show that ``faithful'' randomized rounding of the DkS-variant can be used to round LD2S solutions. Our notion of faithfulness intuitively means that all vertices and edges are chosen with probability proportional to their LP value, but the precise formulation is more subtle. Unfortunately, the best algorithms known for DkS use the Lovasz-Schrijver LP hierarchy in a non-faithful way [Bhaskara, Charikar, Chlamtac, Feige, and Vijayaraghavan, STOC 2010]. Our main technical contribution is to overcome this shortcoming, while still matching the gap that arises in random graphs by planting a sub graph with same log-density.

STOC Conference 2011 Conference Paper

Directed spanners via flow-based linear programs

• Michael Dinitz
• Robert Krauthgamer

We examine directed spanners through flow-based linear programming relaxations. We design an ~O(n 2/3 )-approximation algorithm for the directed k-spanner problem that works for all k ≥ 1, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous ~O(n 1-1/k ) approximation [BGJRW09] when k ≥ 4. For the special case of k=3 we design a different algorithm achieving an ~O(√n)-approximation, improving the previous ~O(n 2/3 ) [EP05,BGJRW09] (independently of our work, an ~O(n 1-1/⌈ k/2⌉ ) was recently devised [BRR10]). Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of ~Ω(n 1/3 - ε ) for every constant ε > 0. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices .

SODA Conference 2009 Conference Paper

Secretary problems: weights and discounts

• Moshe Babaioff
• Michael Dinitz
• Anupam Gupta 0001
• Nicole Immorlica
• Kunal Talwar

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e. g. , the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: • In the discounted secretary problem, there is a time-dependent “discount” factor d ( t ), and the benefit derived from selecting an element/secretary e at time t is d ( t )· v ( e ). For this problem with arbitrary (not necessarily decreasing) functions d ( t ), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of, and give a nearly-matching O (log n )-competitive algorithm. • In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w ( k ), and assigning object/secretary e to position k has benefit w ( k ) · v ( e ). The goal is to select secretaries and assign them to positions to maximize Σ e, k w ( k ) · v ( e ) · x ek where x ek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O (log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e. g. , Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.