>> Publications

Home | Toggle Abstract


  1. Large Fixed-Diameter Graphs are Good Expanders
    | arxiv
    (with Michael Schapira and Gal Shahaf)
    We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction. We show that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "sufficiently large" (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. We discuss the implications of our results for open questions in graph theory and for recent advances in computer networking, and leave the reader with many interesting open questions.
  2. Multicast Capacity Through Perfect Domination
    | arxiv
    (with Naomi Ephraim)
    The capacity of wireless networks is a classic and important topic of study. Informally, the capacity of a network is simply the total amount of information which it can transfer. In the context of models of wireless radio networks, this has usually meant the total number of point-to-point messages which can be sent or received in one time step. This definition has seen intensive study in recent years, particularly with respect to more accurate models of radio networks such as the SINR model. This paper is motivated by an obvious fact: radio antennae are (at least traditionally) omnidirectional, and hence point-to-point connections are not necessarily the best definition of capacity. To fix this, we introduce a new definition of capacity as the maximum number of messages which can be received in one round, and show that this is related to a new optimization problem we call the Maximum Perfect Dominated Set (MaxPDS) problem. Using this relationship we give tight upper and lower bounds for approximating the capacity. We also analyze this notion of capacity under game-theoretic constraints, giving tight bounds on both the Price of Anarchy and the Price of Stability.

Peer-Reviewed Publications:

  1. Timely, Reliable, and Cost-Effective Internet Transport Service using Dissemination Graphs
    ICDCS '17
    (with Amy Babay, Emily Wagner, and Yair Amir)
    Emerging applications such as remote manipulation and remote robotic surgery require communication that is both timely and reliable, but the Internet natively supports only communication that is either completely reliable with no timeliness guarantees (e.g. TCP) or timely with best-effort reliability (e.g. UDP). We present an overlay transport service that can provide highly reliable communication while meeting stringent timeliness guarantees (e.g. 130ms round-trip latency across the US) over the Internet. To enable routing schemes that can support the necessary timeliness and reliability, we introduce dissemination graphs, providing a unified framework for specifying routing schemes ranging from a single path, to multiple disjoint paths, to arbitrary graphs. We conduct an extensive analysis of real-world network data, finding that a routing approach using two disjoint paths performs well in most cases, and that cases where two disjoint paths do not perform well typically involve problems around a source or destination. Based on this analysis, we develop a timely dissemination-graph-based routing method that can add targeted redundancy in problematic areas of the network. This approach can cover over 99% of the performance gap between a traditional single-path approach and an optimal (but prohibitively expensive) scheme, while two dynamic disjoint paths cover about 70% of this gap, and two static disjoint paths cover about 45%. This performance improvement is obtained at a cost increase of about 2% over two disjoint paths.
  2. Load Balancing with Bounded Convergence in Dynamic Networks
    INFOCOM '17
    (with Jeremy Fineman, Seth Gilbert, and Calvin Newport)
    Load balancing is an important activity in distributed systems. At a high-level of abstraction, this problem assumes processes in the system begin with a potentially uneven assignment of "work" which they must then attempt to spread evenly. There are many different approaches to solving this problem. In this paper, we focus on local load balancing---an approach in which work is balanced in an iterative and distributed manner by having processes exchange work in each round with neighbors in an underlying communication network. The goal with local load balancing is to prove that these local exchanges will lead over time to a global balance. We describe and analyze a new local load balancing strategy called max neighbor, and prove a bound on the number of rounds required for it to obtain a parameterized level of balance, with high probability, in a general dynamic network topology. We then prove this analysis tight (within logarithmic factors) by describing a network and initial work distribution for which max neighbor matches its upper bound, and then build on this to prove that no load balancing algorithm in which every node exchanges work with at most one partner per round can converge asymptotically faster than max neighbor.
  3. Approximating Approximate Distance Oracles
    ITCS '17
    | arxiv
    (with Zeyu Zhang)
    Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v \in V, returns an approximation to the the actual distance between $u$ and $v$ which is within some bounded stretch factor of the true distance. There has been significant work on the tradeoff between the important parameters of approximate distance oracles (and in particular between the size, stretch, and query time), but in this paper we take a different point of view, that of per-instance optimization. If we are given an particular input metric space and stretch bound, can we find the smallest possible approximate distance oracle for that particular input? Since this question is not even well-defined, we restrict our attention to well-known classes of approximate distance oracles, and study whether we can optimize over those classes.

    In particular, we give an O(log n)-approximation to the problem of finding the smallest stretch 3 Thorup-Zwick distance oracle, as well as the problem of finding the smallest Patrascu-Roditty distance oracle. We also prove a matching Omega(log n) lower bound for both problems, and an \Omega(n^{\frac{1}{k}-\frac{1}{2^{k-1}}}) integrality gap for the more general stretch $(2k-1)$ Thorup-Zwick distance oracle. We also consider the problem of approximating the best TZ or PR approximate distance oracle with outliers, and show that more advanced techniques (SDP relaxations in particular) allow us to optimize even in the presence of outliers.
  4. Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
    SODA '17
    (with Eden Chlamtac and Yury Makarychev)
    In the Minimum k-Union problem (MkU) 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 O(\sqrt{n})-approximation 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 = \Omega(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 n^{1/4+\eps} approximation for SSBVE for any constant \eps > 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 O~(\sqrt{n}) approximation for the more general SSVE problem (where no non-trivial approximations were known for general k).
  5. Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
    SODA '17
    (with Eden Chlamtac, Guy Kortsarz, and Bundit Laekhanukit)
    It was recently found that there are very close connections between 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-Godwin SODA '16, Godwin-Williams SODA '16]. We study these problems from an optimization point of view, where rather than 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(n3/5 +ϵ)-approximation for distance preservers and pairwise spanners (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(n3/5 + ϵ)-approximation for the Directed Steiner Forest problem (for arbitrary constant ϵ > 0) when all edges have uniform costs, improving the previous best O(n2/3 + ϵ)-approximation due to Berman et al. [ICALP '11] (which holds for general edge costs).
  6. Xpander: Towards Optimal-Performance Datacenters
    CoNext '16
    (with Asaf Valadarsky, Gal Shahaf, and Michael Schapira)
    Despite extensive efforts to meet ever-growing demands, today's datacenters often exhibit far-from-optimal performance in terms of network utilization, resiliency to failures, cost efficiency, incremental expandability, and more. Consequently, many novel architectures for high-performance datacenters have been proposed. We show that the benefits of state-of-the-art proposals are, in fact, derived from the fact that they are (implicitly) utilizing "expander graphs" (aka expanders) as their network topologies, thus unveiling a unifying theme of these proposals. We observe, however, that these proposals are not optimal with respect to performance, do not scale, or suffer from seemingly insurmountable deployment challenges. We leverage these insights to present Xpander, a novel datacenter architecture that achieves near-optimal performance and provides a tangible alternative to existing datacenter designs. Xpander's design turns ideas from the rich graph-theoretic literature on constructing optimal expanders into an operational reality. We evaluate Xpander via theoretical analyses, extensive simulations, experiments with a network emulator, and an implementation on an SDN-capable network testbed. Our results demonstrate that Xpander significantly outperforms both traditional and proposed datacenter designs. We discuss challenges to real-world deployment and explain how these can be resolved.
  7. The Densest k-Subhypergraph Problem
    APPROX '16
    (with Eden Chlamtac, Christian Konrad, Guy Kortsarz, and George Rabanca)
    The Densest k-Subgraph (DkS) problem, and its corresponding minimization problem Smallest p-Edge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out).

    In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest k-Subhypergraph problem (given a hypergraph (V,E), find a subset W⊆V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an O(n4(4−√3)/13+ϵ) ≤ O(n0.697831+ϵ)-approximation (for arbitrary constant ϵ>0) for Densest k-Subhypergraph and an Õ(n2/5)-approximation for Minimum p-Union. We also give an O(√m)-approximation for Minimum p-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.
  8. Computing Approximate PSD Factorizations
    APPROX '16
    (with Amitabh Basu and Xin Li)
    We give an algorithm for computing approximate PSD factorizations of nonnegative matrices. The running time of the algorithm is polynomial in the dimensions of the input matrix, but exponential in the PSD rank and the approximation error. The main ingredient is an exact factorization algorithm when the rows and columns of the factors are constrained to lie in a general polyhedron. This strictly generalizes nonnegative matrix factorizations which can be captured by letting this polyhedron to be the nonnegative orthant.
  9. Approximating Low-Stretch Spanners
    SODA '16
    (with Zeyu Zhang)
    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 Õ(n1/3)-approximation for 4-spanner (both basic and directed). This was the last value of k for which only an O(√n)-approximation was known for basic k-spanner, and thus implies that for any k the approximation ratio is at most Õ(n1/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 n^{\frac{1}{\lfloor (k+1)/2\rfloor}}.

    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).
  10. Xpander: Unveiling the Secrets of High-Performance Datacenters
    HotNets '15
    | ACM DL
    (with Michael Schapira and Asaf Valadarsky)
    Many architectures for high-performance datacenters have been proposed. Surprisingly, recent studies show that datacenter designs with random network topologies outperform more sophisticated designs, achieving near-optimal throughput and bisection bandwidth, high resiliency to failures, incremental expandability, high cost efficiency, and more. Unfortunately, the inherent unstructuredness and unpredictability of random designs pose serious, arguably insurmountable, obstacles to their adoption in practice. Can these guarantees be achieved by well-structured, deterministic datacenters? We provide a surprising affirmative answer. We show,through a combination of theoretical analyses, extensive simulations, and experiments with a network emulator, that any “expander” network topology (as indeed are random graphs) comes with these benefits. We leverage this insight to present Xpander, a novel deterministic datacenter architecture that achieves all of the above desiderata while providing a tangible alternative to existing datacenter designs. We discuss challenges en route to deploying Xpander (including physical layout, cabling costs and complexity, backwards compatibility) and explain how these can be resolved.
  11. Smoothed Analysis of Dynamic Networks
    DISC '15
    | LNCS | arxiv
    (with Jeremy Fineman, Seth Gilbert, and Calvin Newport)
    Invited to special issue of Distributed Computing
    We generalize the technique of smoothed analysis to distributed algorithms in dynamic network models. Whereas standard smoothed analysis studies the impact of small random perturbations of input values on algorithm performance metrics, dynamic graph smoothed analysis studies the impact of random perturbations of the underlying changing network graph topologies. Similar to the original application of smoothed analysis, our goal is to study whether known strong lower bounds in dynamic network models are robust or fragile: do they withstand small (random) perturbations, or do such deviations push the graphs far enough from a precise pathological instance to enable much better performance? Fragile lower bounds are likely not relevant for real-world deployment, while robust lower bounds represent a true difficulty caused by dynamic behavior. We apply this technique to three standard dynamic network problems with known strong worst-case lower bounds: random walks, flooding, and aggregation. We prove that these bounds provide a spectrum of robustness when subjected to smoothing---some are extremely fragile (random walks), some are moderately fragile / robust (flooding), and some are extremely robust (aggregation).
  12. Explicit Expanding Expanders
    ESA '15, Algorithmica
    (with Michael Schapira and Asaf Valadarsky)
    Invited to special issue of Algorithmica
    Deterministic constructions of expander graphs have been an important topic of research in computer science and mathematics, with many well-studied constructions of infinite families of expanders. In some applications, though, an infinite family is not enough: we need expanders which are "close" to each other. We study the following question: Construct an an infinite sequence of expanders G0,G1,…, such that for every two consecutive graphs Gi and Gi+1, Gi+1 can be obtained from Gi by adding a single vertex and inserting/removing a small number of edges, which we call the expansion cost of transitioning from Gi to Gi+1. This question is very natural, e.g., in the context of datacenter networks, where the vertices represent racks of servers, and the expansion cost captures the amount of rewiring needed when adding another rack to the network. We present an explicit construction of d-regular expanders with expansion cost at most 5d/2, for any d≥6. Our construction leverages the notion of a "2-lift" of a graph. This operation was first analyzed by Bilu and Linial, who repeatedly applied 2-lifts to construct an infinite family of expanders which double in size from one expander to the next. Our construction can be viewed as a way to "interpolate" between Bilu-Linial expanders with low expansion cost while preserving good edge expansion throughout. While our main motivation is centralized (datacenter networks), we also get the best-known distributed expander construction in the "self-healing" model.
  13. Towards Resistance Sparsifiers
    RANDOM '15
    (with Robert Krauthgamer and Tal Wagner)
    We study resistance sparsification of graphs, in which the goal is to find a sparse subgraph (with reweighted edges) that approximately preserves the effective resistances between every pair of nodes. We show that every dense regular expander admits a (1+ε)-resistance sparsifier of size Õ(n/ε), and conjecture this bound holds for all graphs on n nodes. In comparison, spectral sparsification is a strictly stronger notion and requires Ω(n/ε2) edges even on the complete graph.

    Our approach leads to the following structural question on graphs: Does every dense regular expander contain a sparse regular expander as a subgraph? Our main technical contribution, which may of independent interest, is a positive answer to this question in a certain setting of parameters. Combining this with a recent result of von Luxburg, Radl, and Hein (JMLR, 2014) leads to the aforementioned resistance sparsifiers.
  14. Lowest Degree k-Spanner: Approximation and Hardness
    APPROX '14, Theory of Computing (journal)
    | ToC | LIPIcs
    (with Eden Chlamtac)
    Invited to special issue of Theory of Computing
    A k-spanner is a subgraph in which distances are approximately preserved, up to some given stretch factor k. We focus on the following problem: Given a graph and a value k, can we find a k-spanner that minimizes the maximum degree? While reasonably strong bounds are known for some spanner problems, they almost all involve minimizing the total number of edges. Switching the objective to the degree introduces significant new challenges, and currently the only known approximation bound is an O~(Delta^{3 - 2sqrt{2}})-approximation for the special case when k=2 [Chlamtac, Dinitz, Krauthgamer FOCS 2012] (where Delta is the maximum degree in the input graph). In this paper we give the first non-trivial algorithm and polynomial-factor hardness of approximation for the case of general k. Specifically, we give an LP-based O~(Delta^{(1-1/k)^2})-approximation and prove that it is hard to approximate the optimum to within Delta^{Omega(1/k)} when the graph is undirected, and to within Delta^{Omega(1)} when it is directed.
  15. Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights
    APPROX '14
    | LIPIcs
    (with Guy Kortsarz and Zeev Nutov)
    In the Steiner k-Forest problem we are given an edge weighted graph, a collection $D$ of node pairs, and an integer $k \leq |D|$. The goal is to find a minimum cost subgraph that connects at least $k$ pairs. The best known ratio for this problem is $\min\{O(\sqrt{n}),O(\sqrt{k})\}$ \cite{GHNR}. In \cite{GHNR} it is also shown that ratio $\rho$ for Steiner k-Forest implies ratio $O(\rho\cdot \log^2 n)$ for the Dial-a-Ride problem: given an edge weighted graph and a set of items with a source and a destination each, find a minimum length tour to move each object from its source to destination, but carrying at most $k$ objects at a time. The only other algorithm known for Dial-a-Ride, besides the one resulting from \cite{GHNR}, has ratio $O(\sqrt{n})$ \cite{CR98}.

    We obtain ratio $n^{0.448}$ for Steiner k-Forest and Dial-a-Ride with unit weights, breaking the $O(\sqrt{n})$ ratio barrier for this natural special case. We also show that if the maximum weight of an edge is $O(n^{\epsilon})$, then one can achieve ratio $O(n^{(1+\epsilon)\cdot 0.448})$, which is less than $\sqrt{n}$ if $\epsilon$ is small enough.

    To prove our main result we consider the following generalization of the Minimum $k$-Edge Subgraph (Mk-ES) problem, which we call Min-Cost $\ell$-Edge-Profit Subgraph (MCl-EPS): Given a graph $G=(V,E)$ with edge-profits $w=\{p_e:e \in E\}$ and node-costs $c=\{c_v:v \in V\}$, and a lower profit bound $\ell$, find a minimum node-cost subgraph of $G$ of edge profit at least $\ell$. The Mk-ES problem is a special case of MCl-EPS with unit node costs and unit edge profits. The currently best known ratio for Mk-ES is $n^{3-2\sqrt{2} + \epsilon}$ (note that $3-2\sqrt{2} < 0.1716$) \cite{CDK}. We extend this ratio to MCl-EPS for arbitrary node weights and edge profits that are polynomial in $n$. This extension is of independent interest.
  16. Braess's Paradox in Wireless Networks: The Danger of Improved Technology
    DISC '13
    | LNCS | arxiv |pdf
    (with Merav Parter)
    When comparing new wireless technologies, it is common to consider the effect that they have on the capacity of the network (defined as the maximum number of simultaneously satisfiable links). For example, it has been shown that giving receivers the ability to do interference cancellation, or allowing transmitters to use power control, never decreases the capacity and can in certain cases increase it by $\Omega(\log (\Delta \cdot P _{\max}))$, where $\Delta$ is the ratio of the longest link length to the smallest transmitter-receiver distance and $P_{\max}$ is the maximum transmission power. But there is no reason to expect the optimal capacity to be realized in practice, particularly since maximizing the capacity is known to be NP-hard. In reality, we would expect links to behave as self-interested agents, and thus it makes more sense to compare the values reached at game-theoretic notions of equilibria than the optimum values.

    In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly "better" technology. We show a version of Braess's Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria worse, despite an increase in the capacity. We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold ($\beta$), and is $\Omega(\log \Delta)$ when power control is combined with interference cancellation. However, we show that these examples are basically tight: the decrease is at most $O(1)$ for power control, interference cancellation, and improved $\beta$, and is at most $O(\log \Delta)$ when power control is combined with interference cancellation.
  17. Packing Interdiction and Partial Covering Problems
    IPCO '13
    | LNCS | pdf
    (with Anupam Gupta)
    In the Packing Interdiction problem we are given a packing LP together with a separate interdiction cost for each LP variable and a global interdiction budget. Our goal is to harm the LP: which variables should we forbid the LP from using (subject to forbidding variables of total interdiction cost at most the budget) in order to minimize the value of the resulting LP? There is a long line of work on interdiction problems in graphs (interdicting the maximum flow, the shortest path, the minimum spanning tree, etc.), but we are the first to consider the problem of interdicting linear programs. The motivation for packing interdiction is matching interdiction, in which we are given a graph with edge weights and edge costs, and try to destroy edges of total cost at most some value B in order to minimize the maximum weight matching of the resulting graph. Zenklusen showed that this problem is NP-hard and gave a 4-approximation when all edge weights are unit. We obtain an O(1)-approximation to the general matching interdiction problem (without the unit weight assumption) as a corollary of our main result, an O(log q \cdot min{q, log k})-approximation to Packing Interdiction where q is the row-sparsity of the packing LP and k is the column-sparsity.
  18. Matroid Secretary for Regular and Decomposable Matroids
    SODA '13, SICOMP (journal)
    (with Guy Kortsarz)
    In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g. graphic and transversal matroids). In particular, there is very little known about F-representable matroids (the class of matroids that can be represented as elements of a vector space over a field F), which are one of the foundational matroid classes. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving an O(1)-competitive algorithm for regular matroids (the class of matroids that are representable over every field), and use techniques that are matroid-theoretic rather than graph-theoretic. We use the regular matroid decomposition theorem of Seymour to decompose any regular matroid into matroids which are either graphic, cographic, or isomorphic to R_{10}, and then show how to combine algorithms for these basic classes into an algorithm for regular matroids. This allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids.
  19. Everywhere-Sparse Spanners via Dense Subgraphs
    FOCS '12
    (with Eden Chlamtac and Robert Krauthgamer)
    Recent significant progress in constructing graph spanners that are sparse (small number of edges) or light (low total weight) has skipped everywhere-sparse spanners (small maximum degree). Similar to other network design problems, this maximum degree objective has turned out to be challenging despite its mathematical simplicity and usefulness in applications. In the Lowest Degree 2-Spanner (LD2S) problem, 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 Õ(Δ^(3-2√2)) ≈ Õ(Δ^(0.172)), where Δ is the maximum degree of the input graph. The previous Õ(Δ^(1/4))$--approximation was proved nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998].

    Our main conceptual contribution is establishing a formal connection between LD2S and a variant of the Densest k-Subgraph (DkS) problem. Specifically, we design for both problems strong relaxations based on Linear Programming (LP) hierarchies, 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 Sherali-Adams 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 subgraph with same log-density.

  20. IBGP and Constrained Connectivity
    APPROX '12
    | LNCS | arxiv
    (with Gordon Wilfong)
    We initiate the theoretical study of the problem of minimizing the size of an IBGP overlay in an Autonomous System (AS) in the Internet subject to a natural notion of correctness derived from the standard "hot-potato" routing rules. For both natural versions of the problem (where we measure the size of an overlay by either the number of edges or the maximum degree) we prove that it is NP-hard to approximate to a factor better than Ω(log n) and provide approximation algorithms with ratio Õ(√(n)). In addition, we give a slightly worse Õ(n^(2/3))$-approximation based on primal-dual techniques that has the virtue of being both fast and good in practice, which we show via simulations on the actual topologies of five large Autonomous Systems.

    The main technique we use is a reduction to a new connectivity-based network design problem that we call Constrained Connectivity. In this problem we are given a graph G=(V,E), and for every pair of vertices u,v \in V we are given a set S(u,v) ⊆ V called the safe set of the pair. The goal is to find the smallest subgraph H of G in which every pair of vertices u,v is connected by a path contained in S(u,v). We show that the IBGP problem can be reduced to the special case of Constrained Connectivity where G = K_n and safe sets are defined geometrically based on the IGP distances in the AS. We also believe that Constrained Connectivity is an interesting problem in its own right, so provide stronger hardness results (2^(log^(1-ε) n)-hardness of approximation) and integrality gaps (n^(1/3 - ε) for the general case. On the positive side, we show that Constrained Connectivity turns out to be much simpler for some interesting special cases other than iBGP: when safe sets are symmetric and hierarchical, we give a polynomial time algorithm that computes an optimal solution.

  21. Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner
    ICALP '12, TALG (journal)
    | TALG | ICALP | arxiv
    (with Guy Kortsarz and Ran Raz)
    We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some k, the problem is roughly 2^{\log^{1-\epsilon} n/k} hard to approximate for all constant \epsilon > 0. A similar theorem was claimed by Elkin and Peleg [ICALP 2000], but their proof was later found to have a fundamental error. Thus for the problem of Label Cover with large girth we give the first non-trivial lower bound. We use the new proof to show inapproximability for the basic k-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP \not\subseteq BPTIME(2^{polylog(n)}), we show (roughly) that for every k \geq 3 and every constant \epsilon > 0 it is hard to approximate the basic k-spanner problem within a factor better than 2^{(\log^{1-\epsilon} n) / k}. A similar hardness for basic k-spanner was claimed by Elkin and Peleg [ICALP 2000], but the error in their analysis of Label Cover made this proof fail as well. For the basic k-spanner problem we improve the previous best lower bound of \Omega(\log n)/k by Kortsarz [1998]. Our main technique is subsampling the edges of 2-query PCPs, which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.
  22. Efficient Computation of Distance Sketches in Distributed Networks
    SPAA '12, Distributed Computing (journal)
    (with Atish Das Sarma and Gopal Pandurangan)
    Distance computation (e.g., computing shortest paths) is one of the most fundamental primitives used in communication networks. The cost of effectively and accurately computing pairwise network distances can become prohibitive in large-scale networks such as the Internet and Peer-to-Peer (P2P) networks. To negotiate the rising need for very efficient distance computation at scales never imagined before, approximation techniques for numerous variants of this question have recently received significant attention in the literature. Several different areas of theoretical research have emerged centered around this problem, such as metric embeddings, distance labelings, spanners, and distance oracles. The goal is to preprocess the graph and store a small amount of information such that whenever a query for any pairwise distance is issued, the distance can be well approximated (i.e., with small stretch) very quickly in an online fashion. Specifically, the pre-processing (usually) involves storing a small sketch with each node, such that at query time only the sketches of the concerned nodes need to be looked up to compute the approximate distance.

    Techniques derived from metric embeddings have been considered extensively by the networking community, usually under the name of network coordinate systems. On the other hand, while the computation of distance oracles has received considerable attention in the context of web graphs and social networks, there has been little work towards similar algorithms within the networking community. In this paper, we present the first theoretical study of distance sketches derived from distance oracles in a distributed network. We first present a fast distributed algorithm for computing approximate distance sketches, based on a distributed implementation of the distance oracle scheme of [Thorup-Zwick, JACM 2005]. We also show how to modify this basic construction to achieve different tradeoffs between the number of pairs for which the distance estimate is accurate, the size of the sketches, and the time and message complexity necessary to compute them. These tradeoffs can then be combined to give an efficient construction of small sketches with provable average-case as well as worst-case performance. Our algorithms use only small-sized messages and hence are suitable for bandwidth-constrained networks, and can be used in various networking applications such as topology discovery and construction, token management, load balancing, monitoring overlays, and several other problems in distributed algorithms.

  23. Fault-Tolerant Spanners: Better and Simpler
    PODC '11
    (with Robert Krauthgamer)
    A natural requirement of many distributed structures is fault-tolerance: after some failures, whatever remains from the structure should still be effective for whatever remains from the network. In this paper we examine spanners of general graphs that are tolerant to vertex failures, and significantly improve their dependence on the number of faults r, for all stretch bounds.

    For stretch k ≥ 3 we design a simple transformation that converts every k-spanner construction with at most f(n) edges into an r-fault-tolerant k-spanner construction with at most O(r^3 log n) ⋅ f(2n/r) edges. Applying this to standard greedy spanner constructions gives r-fault tolerant k-spanners with Õ(r^2 n^(1+(2/(k+1)))) edges. The previous construction by Chechik, Langberg, Peleg, and Roddity [STOC 2009] depends similarly on n but exponentially on r (approximately like k^r).

    For the case k=2 and unit-length edges, an O(r log n)-approximation algorithm is known from recent work of Dinitz and Krauthgamer [STOC 2011], where several spanner results are obtained using a common approach of rounding a natural flow-based linear programming relaxation. Here we use a different (stronger) LP relaxation and improve the approximation ratio to O(log n), which is, notably, independent of the number of faults r. We further strengthen this bound in terms of the maximum degree by using the Lovasz Local Lemma.

    Finally, we show that most of our constructions are inherently local by designing equivalent distributed algorithms in the LOCAL model of distributed computation.

  24. Directed Spanners via Flow-Based Linear Programs
    STOC '11
    (with Robert Krauthgamer)
    We examine directed spanners through flow-based linear programming relaxations. We design an Õ(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 Õ(n^(1-1/k)) approximation of Bhattacharyya et al. when k ≥ 4. For the special case of k=3 we design a different algorithm achieving an Õ(n^(1/2))-approximation, improving the previous Õ(n^(2/3)). 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 any 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.

  25. Distributed Algorithms for Approximating Wireless Network Capacity
    INFOCOM '10
    doi | pdf
    In this paper we consider the problem of maximizing wireless network capacity (a.k.a. one-shot scheduling) in both the protocol and physical models. We give the first distributed algorithms with provable guarantees in the physical model, and show how they can be generalized to more complicated metrics and settings in which the physical assumptions are slightly violated. We also give the first algorithms in the protocol model that do not assume transmitters can coordinate with their neighbors in the interference graph, so every transmitter chooses whether to broadcast based purely on local events. Our techniques draw heavily from algorithmic game theory and machine learning theory, even though our goal is a distributed algorithm. Indeed, our main results allow every transmitter to run any algorithm it wants, so long as its algorithm has a learning-theoretic property known as no-regret in a game-theoretic setting.
  26. Graphical Representations of Clutters
    Ars Combinatoria (2010)
    (with Jonah Gold, Thomas Sharkey, and Lorenzo Traldi)
    We discuss the use of K-terminal networks to represent arbitrary clutters. A given clutter has many different representations, and there does not seem to be any set of simple transformations that can be used to transform one representation of a clutter into any other. We observe that for t ≥ 2 the class of clutters that can be represented using no more than t terminals is closed under minors, and has infinitely many forbidden minors.
  27. Maximizing Capacity in Arbitrary Wireless Networks in the SINR Model: Complexity and Game Theory
    INFOCOM '09
    doi | pdf
    (with Matthew Andrews)
    In this paper we consider the problem of maximizing the number of supported connections in arbitrary wireless networks where a transmission is supported if and only if the signal-to-interference-plus-noise ratio at the receiver is greater than some threshold. The aim is to choose transmission powers for each connection so as to maximize the number of connections for which this threshold is met.

    We believe that analyzing this problem is important both in its own right and also because it arises as a subproblem in many other areas of wireless networking. We study both the complexity of the problem and also present some game theoretic results regarding capacity that is achieved by completely distributed algorithms. We also feel that this problem is intriguing since it involves both continuous aspects (i.e. choosing the transmission powers) as well as discrete aspects (i.e. which connections should be supported). Our results are:

    —We show that maximizing the number of supported connections is NP-hard, even when there is no background noise. This is in contrast to the problem of determining whether or not a given set of connections is feasible since that problem can be solved via linear programming.

    —We present a number of approximation algorithms for the problem. All of these approximation algorithms run in polynomial time and have an approximation ratio that is independent of the number of connections.

    —We examine a completely distributed algorithm and analyze it as a game in which a connection receives a positive payoff if it is successful and a negative payoff if it is unsuccessful while transmitting with nonzero power. We show that in this game there is not necessarily a pure Nash equilibrium but if such an equilibrium does exist the corresponding price of anarchy is independent of the number of connections. We also show that a mixed Nash equilibrium corresponds to a probabilistic transmission strategy and in this case such an equilibrium always exists and has a price of anarchy that is independent of the number of connections.

  28. Secretary Problems: Weights and Discounts
    SODA '09
    (with Moshe Babaioff, Anupam Gupta, Nicole Immorlica, and 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) 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 Ω(log n/log log n), 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 the total benefit. We give constant-competitive algorithms for this problem.

    Most of these results can also be extended to the matroid secretary case (Babaioff et al.) 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.). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

  29. Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
    DISC '08
    doi | pdf
    The theoretical computer science community has traditionally used embeddings of finite metrics as a tool in designing approximation algorithms. Recently, however, there has been considerable interest in using metric embeddings in the context of networks to allow network nodes to have more knowledge of the pairwise distances between other nodes in the network. There has also been evidence that natural network metrics like latency and bandwidth have some nice structure, and in particular come close to satisfying an ε-three point condition or an ε-four point condition. This empirical observation has motivated the study of these special metrics, including strong results about embeddings into trees and ultrametrics. Unfortunately all of the current embeddings require complete knowledge about the network up front, and so are less useful in real networks which change frequently. We give the first metric embeddings which have both low distortion and require only small changes in the structure of the embedding when the network changes. In particular, we give an embedding of semimetrics satisfying an ε-three point condition into ultrametrics with distortion (1 + ε)^(log n  +  4) and the property that any new node requires only O(n^(1/3)) amortized edge swaps, where we use the number of edge swaps as a measure of “structural change”. This notion of structural change naturally leads to small update messages in a distributed implementation in which every node has a copy of the embedding. The natural offline embedding has only (1 + ε)^(log n) distortion but can require Ω(n) amortized edge swaps per node addition. This online embedding also leads to a natural dynamic algorithm that can handle node removals as well as insertions.
  30. Compact Routing with Slack
    PODC '07
    Given a weighted graph G=(V,E), a compact routing scheme is a distributed algorithm for forwarding packets from any source to any destination. The fundamental tradeoff is between the space used at each node and the stretch of the total route, measured by the multiplicative factor between the actual distance traveled and the length of the shortest possible route. We extend the normal definition with a slack parameter ε, which allows us to ignore up to εn^2 of the shortest pairwise routes and give a guarantee on the remaining ones. For constant ε we give constant stretch, polylogarithmic space schemes in the name-dependent model and in the designer-port name-independent model, and give a lower bound that proves that such schemes do not exist in the fixed-port name-independent model. In the name-dependent model we also give a gracefully degrading scheme which works simultaneously for all ε > 0 and guarantees constant average stretch with polylog space.
  31. Spanners with Slack
    ESA '06
    doi | pdf
    (with T-H. Hubert Chan and Anupam Gupta)
    Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into ℓ p spaces. For instance, we show that if we ignore an ε fraction of the distances, we can get spanners with O(n) edges and O(log(1/ε)) distortion for the remaining distances.

    We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces.

  32. Full rank tilings of finite abelian groups
    SIAM Journal on Discrete Mathematics (2006)
    doi | pdf
    A tiling of a finite abelian group G is a pair (V,A) of subsets of G such that 0 is in both V and A and every g ∈ G can be uniquely written as g=v+a with v ∈ V and a ∈ A. Tilings are a special case of normed factorizations, a type of factorization by subsets that was introduced by Hajós [Casopsis Puest Path. Rys., 74, (1949), pp. 157-162]. A tiling is said to be full rank if both V and A generate G. Cohen, Litsyn, Vardy, and Zémor [SIAM J. Discrete Math., 9 (1996), pp. 393-412] proved that any tiling of Z_2^n can be decomposed into full rank and trivial tilings. We generalize this decomposition from Z_2^n to all finite abelian groups. We also show how to generate larger full rank tilings from smaller ones, and give two sufficient conditions for a group to admit a full rank tiling, showing that many groups do admit them. In particular, we prove that if p ≥ 5 is a prime and n ≥ 4, then Z_p^n admits a full rank tiling. This bound on n is tight for 5 ≤ p ≤ 11, and is conjectured to be tight for all primes p.
  33. Enumeration of Balanced Tournament Designs on 10 points
    Journal of Combinatorial Mathematics and Combinatorial Computing (2005)
    (with Jeffrey Dinitz)
    We enumerate the balanced tournament designs on 10 points (BTD(5)) and find that there are exactly 30,220,557 nonisomorphic designs. We also find that there are exactly two nonisomorphic partitioned BTD(5)'s and 8,081,114 factored BTD(5)'s on 10 points. We enumerate other classes of balanced tournament designs on 10 points and give examples of some of the more interesting ones. In 1988 Corriveau enumerated the nonisomorphic BTD(4)'s finding that there are 47 of them. This paper enumerates the next case and provides another good example of the combinatorial explosion phenomenon.


  1. Recent Advances on the Matroid Secretary Problem
    SIGACT News (2013)
    | ACM DL | pdf
    The matroid secretary problem was introduced by Babaioff, Immorlica, and Kleinberg in SODA 2007 as an online problem that was both mathematically interesting and had applications to online auctions. In this column I will introduce and motivate this problem, and give a survey of some of the exciting work that has been done on it over the past 6 years. While we have a much better understanding of matroid secretary now than we did in 2007, the main conjecture is still open: does there exist an O(1)-competitive algorithm?

Just for fun:

  1. Highly efficient and effective removal of fat from fried chicken via centrifugation
    Annals of Improbable Research (2013)
    | pdf
    (with Lucas Carey and Desiree Tillo)
    Approximately 20% of Israelis and >30% of Americans are obese and deep fried foods contribute a significant fraction of the daily fat intake. Fried chicken is a popular high fat food and contributes to a significant fraction of daily fat consumption. Indeed, an increase in fried chicken consumption has been blamed for contributing to the increase in obesity in both China and the Arabian Peninsula. Most current research on reducing the fat in fried chicken has focused on reducing fat uptake during the frying process, however, these methods have not been adopted by restaurants or consumers. Here we present centrifugation of the already cooked fried chicken as an alternative method for fat reduction. We show that centrifugation of fried chicken reduces the fat content. This method, in contrast to all existing methods that target food preparation and cooking, can be applied to already fried chicken, thus providing the first method that can be used directly by consumers with access to a centrifuge.
  2. An Incentive-Compatible Mechanism for all Settings: Chuck Norris
    SIGBOVIK '08
    | pdf
    A very important property for any mechanism is incentive-compatibility. A mechanism is incentive-compatible if no agent has an incentive not to follow the protocol. In this paper we present a new meta-mechanism that can be applied to any existing mechanism to make it incentive compatible. This meta-mechanism is Chuck Norris. This shows that any mechanism can be made incentive-compatible, and thus the field of mechanism design is now solved.
  3. Slacking with Slack
    SIGBOVIK '08
    | pdf
    The classical graduate student problem is the well-studied problem of how a graduate student can spend all of their time slacking off in graduate school while still graduating. A famous impossibility result of Bovik states that if all of a student’s time is spent slacking, then it is impossible to graduate. We relax this problem by adding a slack parameter ε, representing the fraction of time that the student has to spend working. On this ε fraction we make no guarantee at all about the enjoyment of the student, but this enables us to guarantee graduation while also guaranteeing large enjoyment on the other 1 - ε fraction of the time.