## News

May '21: My paper with Christos Papadimitriou, Tristan Pollner and Amin Saberi, "Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities", was accepted to EC 2021.
Apr. '21: My paper with Amin Saberi, "The Greedy Algorithm is not optimal for On-Line Edge Coloring", was accepted to ICALP 2021.
Apr. '21: My paper with Bernhard Haeupler and Ellis Hershkowitz, "Near-Optimal Schedules for Simultaneous Multicasts", was accepted to ICALP 2021.
Feb. '21: I will be serving on the Program Committee for SODA 2022.
Feb. '21: My paper with Bernhard Haeupler and Goran Zuzic, "Universally-Optimal Distributed Algorithms for Known Topologies", was accepted to STOC 2021!
Oct. '20: I will be serving on the Program Committee for HALG (Highlights of Algorithms) 2021.
Sep. '20: My paper with Roie Levin, "Streaming Submodular Matching Meets the Primal-Dual Method", was accepted to SODA 2021.
Sep. '20: My paper with Sayan Bhattacharya and Fabrizio Grandoni, "Online Algorithms for Edge Coloring via the Nibble Method", was accepted to SODA 2021.
Sep. '20 Started my postdoc at Stanford (remotely).
July '20: My paper with Bernhard Haeupler and Goran Zuzic, "Network Coding Gaps for Completion Times of Multiple Unicasts", was accepted to FOCS 2020!
Feb. '20: My paper, "Rounding Dynamic Matchings Against an Adaptive Adversary", was accepted to STOC 2020!
Jan. '20: I will be serving on the Program Committee for ESA 2020.
June '19: My paper with Ilan R. Cohen and Binghui Peng, "Tight Bounds for Online Edge Coloring", was accepted to FOCS 2019!
June '19: My paper with Buddhima Gamlath, Michael Kapralov, Andreas Maggiori and Ola Svensson, "Online Matching with General Arrivals", was accepted to FOCS 2019!

## Contact Information

wajc@stanford.edu

#### Beating the Folklore Algorithm for Dynamic Matching

Mohammad Roghani, Amin Saberi, David Wajc
W3

#### Abstract

The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence 2-approximate) matching in O(n) worst-case update time in n-node graphs.

We present the first deterministic algorithm which outperforms the folklore algorithm in terms of both approximation ratio and worst-case update time. Specifically, we give a (2-Ω(1))-approximate algorithm with O(\sqrt{n}\sqrt[8]{m})=O(n^{3/4}) worst-case update time in n-node, m-edge graphs. For sufficiently small constant ɛ>0, no deterministic (2+ɛ)-approximate algorithm with worst-case update time O(n^{0.99}) was known. Our second result is the first deterministic (2+ɛ)-approximate (weighted) matching algorithm with O_ɛ(1)\cdot O(\sqrt[4]{m}) = O_ɛ(1)\cdot O(\sqrt{n}) worst-case update time.

#### A Randomness Threshold for Online Bipartite Matching, via Lossless Online Rounding

Niv Buchbinder, Joseph (Seffi) Naor, David Wajc
W2

#### Abstract

Over three decades ago, Karp, Vazirani and Vazirani (STOC'90) introduced the online bipartite matching problem. They observed that deterministic algorithms' competitive ratio for this problem is no greater than 1/2, and proved that randomized algorithms can do better. A natural question thus arises: how random is random? i.e., how much randomness is needed to outperform deterministic algorithms? The RANKING algorithm of Karp et al.~requires Õ(n) random bits, which, ignoring polylog terms, remained unimproved. On the other hand, Pena and Borodin (TCS'19) established a lower bound of (1−o(1))loglogn random bits for any 1/2+Ω(1) competitive ratio.

We close this doubly-exponential gap, proving that, surprisingly, the lower bound is tight. In fact, we prove a \emph{sharp threshold} of (1±o(1))loglogn random bits for the randomness necessary and sufficient to outperform deterministic algorithms for this problem, as well as its vertex-weighted generalization. This implies the same threshold for the advice complexity (nondeterminism) of these problems.

Similar to recent breakthroughs in the online matching literature, for edge-weighted matching (Fahrbach et al.~FOCS'20) and adwords (Huang et al.~FOCS'20), our algorithms break the barrier of 1/2 by randomizing matching choices over two neighbors. Unlike these works, our approach does not rely on the recently-introduced OCS machinery, nor the more established randomized primal-dual method. Instead, our work revisits a highly-successful online design technique, which was nonetheless under-utilized in the area of online matching, namely (lossless) online rounding of fractional algorithms. While this technique is known to be hopeless for online matching in general, we show that it is nonetheless applicable to carefully designed fractional algorithms with additional (non-convex) constraints.

#### The Stationary Prophet Inequality Problem

Kristen Kessel, Amin Saberi, Ali Shameli, David Wajc
W1

#### Abstract

We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller.

Our main results are pricing-based policies which (i) achieve a 1/2-approximation of the optimal oine policy, which is best possible, and (ii) achieve a better than (1-1/e)-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a 1-1/e bound implied by recent work of Aouad and Saritaç (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.

#### Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

Christos Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc
C21EC 2021

#### Abstract

The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a “prophet” who knows the future. An equally-natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it?

Motivated by applications in ride hailing, we study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. This problem was recently introduced by Ezra, Feldman, Gravin and Tang (EC’20), who gave a 1/2-competitive algorithm for it. This is the best possible ratio, as this problem is a generalization of the original single-item prophet inequality.

We present a polynomial-time algorithm which approximates optimal online within a factor of 0.51—beating the best-possible prophet inequality. At the core of our result are a new linear program formulation, an algorithm that tries to match the arriving vertices in two attempts, and an analysis that bounds the correlation resulting from the second attempts. In contrast, we show that it is PSPACE-hard to approximate this problem within some constant α<1.

#### The Greedy Algorithm is not optimal for On-Line Edge Coloring

Amin Saberi, David Wajc
C20ICALP 2021

#### Abstract

Nearly three decades ago, Bar-Noy, Motwani and Naor showed that no online edge-coloring algorithm can edge color a graph optimally. Indeed, their work, titled "the greedy algorithm is optimal for on-line edge coloring", shows that the competitive ratio of 2 of the naïve greedy algorithm is best possible online. However, their lower bound required bounded-degree graphs, of maximum degree Δ = O(log n), which prompted them to conjecture that better bounds are possible for higher-degree graphs. While progress has been made towards resolving this conjecture for restricted inputs and arrivals or for random arrival orders, an answer for fully general adversarial arrivals remained elusive.

We resolve this thirty-year-old conjecture in the affirmative, presenting a (1.9+o(1))-competitive online edge coloring algorithm for general graphs of degree Δ=ω(log n) under vertex arrivals. At the core of our results, and of possible independent interest, is a new online algorithm which rounds a fractional bipartite matching x online under vertex arrivals, guaranteeing that each edge e is matched with probability (1/2+c) x_e, for a constant c>0.027.

#### Near-Optimal Schedules for Simultaneous Multicasts

Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
C19ICALP 2021

#### Abstract

We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible.

This is a natural generalization of the seminal work of Leighton, Maggs and Rao, which solved this problem for unicasts, i.e., the case where all trees are paths. They showed the existence of asymptotically optimal O(C + D)-length schedules, where the congestion C is the maximum number of packets sent over an edge and the dilation D is the maximum depth of a tree. This improves over the trivial O(CD) length schedules.

We prove a lower bound for multicasts, which shows that there do not always exist schedules of non-trivial length, o(CD). On the positive side, we construct O(C+D+log^2 n)-length schedules in any n-node network. These schedules are near-optimal, since our lower bound shows that this length cannot be improved to O(C+D) + o(log n).

#### Universally-Optimal Distributed Algorithms for Known Topologies

Bernhard Haeupler, David Wajc, Goran Zuzic
C18STOC 2021

#### Abstract

Many recent distributed optimization algorithms achieve existentially-optimal running times which cannot be improved on some pathological worst-case topologies. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions:

• What network topology parameters determine the complexity of distributed optimization?
• Are there universally-optimal algorithms that are as fast as possible on every topology?
We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1 + ɛ)-min cut, various approximate shortest paths problems, sub-graph connectivity, etc.

In particular, we provide several graph parameters and show that they are equivalent and tight universal lower bounds for the above problems, and therefore fully characterize their inherent complexity, for any given network topology. Our results also imply that algorithms based on low-congestion shortcuts are universally-optimal, if shortcuts are efficiently approximable. We show that this is the case if the topology is known - giving universally-optimal algorithms for all above problems.

#### Streaming Submodular Matching Meets the Primal-Dual Method

Roie Levin, David Wajc
C17SODA 2021

#### Abstract

We study streaming submodular maximization subject to matching/b-matching constraints (MSM/MSbM), and present improved upper and lower bounds for these problems. On the upper bounds front, we give primal-dual algorithms achieving the following approximation ratios.

• 3+2√2≈5.828 for monotone MSM, improving the previous best ratio of 7.75.
• 4+2√3≈7.464 for non-monotone MSM, improving the previous best ratio of 9.899.
• 3+ϵ for maximum weight b-matching, improving the previous best ratio of 4+ϵ.
On the lower bounds front, we improve on the previous best lower bound of e/(e−1)≈1.582 for MSM, and show ETH-based lower bounds of ≈1.914 for polytime monotone MSM streaming algorithms.

Our most substantial contributions are our algorithmic techniques. We show that the (randomized) primal-dual method, which originated in the study of maximum weight matching (MWM), is also useful in the context of MSM. To our knowledge, this is the first use of primal-dual based analysis for streaming submodular optimization. We also show how to reinterpret previous algorithms for MSM in our framework; hence, we hope our work is a step towards unifying old and new techniques for streaming submodular maximization, and that it paves the way for further new results.

#### Online Algorithms for Edge Coloring via the Nibble Method

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
C16SODA 2021

#### Abstract

Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured that an online (1+o(1))Δ-edge-coloring algorithm exists for n-node graphs of maximum degree Δ=ω(log n). This conjecture remains open in general, though it was recently proven for bipartite graphs under one-sided vertex arrivals by Cohen et al. [FOCS'19]. In a similar vein, we study online edge coloring under widely-studied relaxations of the online model.

Our main result is in the random-order online model. For this model, Aggarwal et al. [FOCS'03] gave a (1+o(1))Δ-coloring algorithm for multigraphs with Δ=ω(n^2), and Bahmani et al. [SODA'10] gave a 1.26Δ-coloring algorithm for Δ=ω(log n). Whether the number of colors of Aggarwal et al. and the degree bound of Bahmani et al. could be achieved simultaneously (thus resolving the Bar-Noy et al. conjecture under random-order arrivals) remained open. In this work, we answer this open question in the affirmative; we present an online algorithm that, for some constant γ < 1, uses Δ+O(Δγ log1-γ n) = (1+o(1))Δ colors, w.h.p.

Our second result concerns the adversarial online (and even dynamic) model with recourse. Here, the algorithm is allowed to recolor a small number of edges per edge arrival/departure (this number is referred to as recourse). For this problem, a recent algorithm of Duan et al. [SODA'19] yields a (1+ε)Δ-edge-coloring with poly(log n/ε) recourse. In this work, we given an algorithm that achieves the same with poly(1/ε) recourse. In particular, we remove the dependence on n.

Underlying our results is one common offline algorithm, which we show how to implement efficiently for these two online models. Our algorithm, based on the Rödl Nibble Method, is an adaptation of the distributed algorithm of Dubhashi et al. [TCS'98]. The Nibble Method has been highly successful in the distributed edge coloring literature, and we display its usefulness in the context of online algorithms.

#### Network Coding Gaps for Completion Time of Multiple Unicasts

Bernhard Haeupler, David Wajc, Goran Zuzic
C15FOCS 2020

#### Abstract

We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing.

While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of k unicasts, proving this gap is at most polylogarithmic in k. Complementing this result, we show there exist instances of k unicasts for which this coding gap is polylogarithmic in k. Our results also hold for average completion time, and more generally any ell_p norm of completion times.

David Wajc
C14STOC 2020

#### Abstract

We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against adaptive adversaries. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries (the first such algorithms, as all previous randomized algorithms for this problem assumed an oblivious adversary). In particular, for any constant ɛ>0, our framework yields (2+ɛ)-approximate algorithms with constant update time or polylog worst-case update time, as well as (2-ɛ)-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time, with all these algorithms' guarantees holding against adaptive adversaries. All these results achieve polynomially better update time to approximation tradeoffs than previously known to be achievable against adaptive adversaries.

#### Online Matching with General Arrivals

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc
C13FOCS 2019

#### Abstract

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging, and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following.

1. For edge arrivals, randomization does not help | no randomized algorithm is better than 1/2 competitive.
2. For general vertex arrivals, randomization helps | there exists a randomized (1/2+ Ω(1))-competitive online matching algorithm.

#### Tight Bounds for Online Edge Coloring

Ilan Reuven Cohen, Binghui Peng, David Wajc
C12FOCS 2019

#### Abstract

Vizing’s celebrated theorem asserts that any graph of maximum degree  admits an edge coloring using at most Δ+1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2Δ-1 colors, is optimal among online algorithms. Their lower bound has a caveat, however: it only applies to low-degree graphs, with Δ = O(log n), and they conjectured the existence of online algorithms using (1+o(1))·Δ colors for Δ = ω(log n). Progress towards resolving this conjecture was only made under stochastic arrivals (Aggarwal et al., FOCS’03 and Bahmani et al., SODA’10).

We resolve the above conjecture for adversarial vertex arrivals in bipartite graphs, for which we present a (1+o(1))·Δ-edge-coloring algorithm for Δ = ω(log n) known a priori. Surprisingly, if Δ is not known ahead of time, we show that no online (e/(e-1)-Ω(1))·Δ-edge-coloring algorithm exists. We then provide an optimal, (e/(e-1)+o(1))·Δ-edge-coloring algorithm for unknown Δ = ω(log n). Key to our results, and of possible independent interest, is a novel fractional relaxation for edge coloring, for which we present optimal fractional online algorithms and a near-lossless online rounding scheme, yielding our optimal randomized algorithms.

#### Stochastic Online Metric Matching

Anupam Gupta, Guru Guruganesh, Binguhi Peng, David Wajc
C11ICALP 2019

#### Abstract

We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a xed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching.

Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight O(log n)-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of O(log n) has long been conjectured and remains a tantalizing open question.

In this paper, we show improved results in the i.i.d arrival model. We show how the i.i.d model can be used to give substantially better algorithms: our main result is an O((log log log n)2)- competitive algorithm in this model. Along the way we give a 9-competitive algorithm for the line and tree metrics. Both results imply a strict separation between the i.i.d model and the adversarial and random order models, both for general metrics and these much-studied metrics.

#### Simplified and Space-Optimal Semi-Streaming (2+ε)-Approximate Matching

Mohsen Ghaffari, David Wajc
C10SOSA 2019

#### Abstract

In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass (2+ɛ)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses O(n log^2 n) bits of space, for any constant ɛ>0.

We present two simplified and more intuitive analyses, for essentially the same algorithm, which also improve the space complexity to the optimal bound of O(n log n) bits --- this is optimal as the output matching requires \Omega(n log n) bits. Our analyses rely on a simple use of the primal dual method and a simple accounting method.

Joseph (Seffi) Naor, David Wajc
J2TEAC 2018 Special Issue on EC 15 . Supersedes the EC 15 paper below.

#### Abstract

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than (1-1/e)-competitive ([Karp et al. 1990; Mehta et al. 2007]), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by [Buchbinder et al. 2007), graphs which we call (k,d)-bounded. In such graphs the maximal degree on the online side is at most d and the minimal degree on the offline side is at least k. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio 1-(d-1)/(k+d-1), tending to one as d/k tends to zero. We prove this bound is tight for these algorithms.

Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio 1-(1-1/d)k>1-1/e^{k/d}, or exponentially better loss as a function of k/d, and strictly better than 1-1/e whenever k ≥ d. We complement our lower bounds with matching upper bounds for the vertex- weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well- behaved online packing problems.

#### Round- and Message-Optimal Distributed Graph Algorithms

Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
C9PODC 2018

#### Abstract

Distributed graph algorithms that separately optimize for either the number of rounds used or the total number of messages sent have been studied extensively. However, algorithms simultaneously efficient with respect to both measures have been elusive. For example, only very recently was it shown that for Minimum Spanning Tree (MST), an optimal message and round complexity is achievable (up to polylog terms) by a single algorithm in the CONGEST model of communication.

In this paper we provide algorithms that are simultaneously round- and message-optimal for a number of well-studied distributed optimization problems. Our main result is such a distributed algorithm for the fundamental primitive of computing simple functions over each part of a graph partition. From this algorithm we derive round- and message-optimal algorithms for multiple problems, including MST, Approximate Min-Cut and Approximate Single Source Shortest Paths, among others. On general graphs all of our algorithms achieve worst-case optimal ˜O(D+sqrt{n}) round complexity and ˜O(m) message complexity. Furthermore, our algorithms require an optimal ˜O(D) rounds and ˜O(n) messages on planar, genus-bounded, treewidth-bounded and pathwidth-bounded graphs.

#### Fully-Dynamic Bin Packing with Limited Repacking

Anupam Gupta, Guru Guruganesh, Amit Kumar, David Wajc
C8ICALP 2018

#### Abstract

We study the classic Bin Packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost ci≥0, and we want to use α·OPT bins and incur a movement cost γ·ci, either in the worst case, or in an amortized sense, for α, γ as small as possible. We call γ the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic Bin Packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeoffs between number of bins used and number of items repacked, as well as natural extensions of the latter measure.

#### Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
C7ICALP 2018

#### Abstract

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic “approximately-maximal” fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic (2+ɛ)-approximate integral matching algorithm with small polylog worst-case update time. For the (2+ɛ)-approximation regime only a fractional fullydynamic (2+ɛ)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.

#### Randomized Online Matching in Regular Graphs

Ilan R. Cohen, David Wajc
C6SODA 2018

#### Abstract

In this paper we study the classic online matching problem, introduced in the seminal work of Karp, Vazirani and Vazirani (STOC 1990), in regular graphs. For such graphs, an optimal deterministic algorithm as well as efficient algorithms under stochastic input assumptions were known. In this work, we present a novel randomized algorithm with competitive ratio tending to one on this family of graphs, under adversarial arrival order. Our main contribution is a novel algorithm which achieves competitive ratio 1-O(sqrt(log d)/ sqrt(d)) in expectation on d-regular graphs. In contrast, we show that all previously-studied online algorithms have competitive ratio strictly bounded away from one. Moreover, we show the convergence rate of our algorithm’s competitive ratio to one is nearly tight, as no algorithm achieves competitive ratio better than 1-O(1/sqrt(d)). Finally, we show that our algorithm yields a similar competitive ratio with high probability, as well as guaranteeing each vertex a probability of being matched tending to one.

#### Approximation-Variance Tradeoffs in Facility Location Games

Ariel Procaccia, David Wajc, Hanrui Zhang
C5AAAI 2018

#### Abstract

We revisit the well-studied problem of constructing strategyproof approximation mechanisms for facility location games, but offer a fundamentally new perspective by considering risk averse designers. Specifically, we are interested in the tradeoff between a randomized strategyproof mechanism’s approximation ratio, and its variance (which has long served as a proxy for risk). When there is just one facility, we observe that the social cost objective is trivial, and derive the optimal tradeoff with respect to the maximum cost objective. When there are multiple facilities, the main challenge is the social cost objective, and we establish a surprising impossibility result: under mild assumptions, no smooth approximation-variance tradeoff exists. We also discuss the implications of our work for computational mechanism design at large.

Bernhard Haeupler, David Wajc
C4PODC 2016

#### Abstract

We present a faster distributed broadcasting primitive for the classical radio network model.

The most basic distributed radio network broadcasting primitive - called Decay - dates back to PODC'87 result of Bar-Yehuda, Goldreich, and Itai. In any radio network with some informed source nodes, running Decay for O(d log n + log^2 n) rounds informs all nodes at most d hops away from a source with high probability. Since 1987 this primitive has been the most important building block for implementing many other functionalities in radio networks. The only improvements to this decades-old algorithm are slight variations due to [Czumaj, Rytter; FOCS'03] and [Kowalski and Pelc, PODC'03] which achieve the same functionality in O(d log(n/d) + log^2 n) rounds. To obtain a speedup from this, d and thus also the network diameter need to be near linear, i.e., larger than n^(1-eps).

Our new distributed primitive spreads messages for d hops in O(d (log n log log n)/(log d) + log^{O(1)} n) rounds with high probability. This improves over Decay for any super-polylogarithmic d = log^{omega(1)} n and achieves near-optimal O(d log log n) running time for d = n^eps. This also makes progress on an open question of Peleg.

Joseph (Seffi) Naor, David Wajc
C3EC 2015

#### Abstract

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than (1-1/e)-competitive ([Karp et al. 1990; Mehta et al. 2007]), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by [Buchbinder et al. 2007), graphs which we call (k,d)-bounded. In such graphs the maximal degree on the online side is at most d and the minimal degree on the offline side is at least k. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio 1-(d-1)/(k+d-1), tending to one as d/k tends to zero. We prove this bound is tight for these algorithms.

Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio 1-(1-1/d)k>1-1/e^{k/d}, or exponentially better loss as a function of k/d, and strictly better than 1-1/e whenever k ≥ d. We complement our lower bounds with matching upper bounds for the vertex- weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well- behaved online packing problems.

#### You Will Get Mail! Predicting the Arrival of Future Email

Iftah Gamzu, Zohar Shay Karnin, Yoelle Maarek, David Wajc
C2WWW (Companion Volume) 2015

#### Abstract

The majority of Web email is known to be generated by machines even when one excludes spam. Many machine-generated email messages such as invoices or travel itineraries are critical to users. Recent research studies establish that causality relations between certain types of machine- generated email messages exist and can be mined. These relations exhibit a link between a given message to a past message that gave rise to its creation. For example, a shipment notification message can often be linked to a past online purchase message. Instead of studying how an incoming message can be linked to the past, we propose here to focus on predicting future email arrival as implied by causality relations. Such a prediction method has several potential applications, ranging from improved ad targeting in up sell scenarios to reducing false positives in spam detection.

We introduce a novel approach for predicting which types of machine-generated email messages, represented by so-called "email templates", a user should receive in future time windows. Our prediction approach relies on (1) statistically inferring causality relations between email templates, (2) building a generative model that explains the inbox of each user using those causality relations, and (3) combining those results to predict which email templates are likely to appear in future time frames. We present preliminary experimental results and some data insights obtained by analyzing several million inboxes of Yahoo Mail users, who voluntarily opted-in for such research.

#### Best-Response Dynamics Out of Sync: Complexity and Characterization

Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc
C1EC 2013

#### Abstract

In many computational and economic models of multi-agent interaction, each participant repeatedly "best-responds" to the others' actions. Game theory research on the prominent "best-response dynamics" model typically relies on the premise that the interaction between agents is somehow synchronized. However, in many real-life settings, e.g., internet protocols and large-scale markets, the interaction between participants is asynchronous. We tackle the following important questions: (1) When are best-response dynamics guaranteed to converge to an equilibrium even under asynchrony? (2) What is the (computational and communication) complexity of verifying guaranteed convergence? We show that, in general, verifying guaranteed convergence is intractable. In fact, our main negative result establishes that this task is undecidable. We exhibit, in contrast, positive results for several environments of interest, including complete, computationally-tractable, characterizations of convergent systems. We discuss the algorithmic implications of our results, which extend beyond best-response dynamics to applications such as asynchronous Boolean circuits.

#### On the complexity of vertex-coloring edge-weightings

Andrzej Dudek, David Wajc
J1Discrete Mathematics & Theoretical Computer Science 2011

#### Abstract

Given a graph G=(V,E) and a weight function w:E →R, a coloring of vertices of G, induced by w, is defined by χw(v) = ∑_{e∋v} w(e) for all v∈V. In this paper, we show that determining whether a particular graph has a weighting of the edges from {1,2} that induces a proper vertex coloring is NP-complete.

#### Abstract

In these notes we present the notion of Negative Association, discuss some of its useful properties, and end with some example applications. The slogan to bear in mind here is “independent, or better”.

I have had the pleasure of teaching various courses, both at the Technion and at CMU.

At Carnegie Mellon:

Spring 2019

Probability and Computing (15-359/659):
Spring 2015

At the Technion:

Data Structures 1 (234218):

Summer 2011Summer 2010

Introduction to Systems Programming (234122):
Spring 2009

Introduction to CS (234114):

How do you pronounce 'Wajc'?", you ask?
Answer: The second syllable of the words e-vites and invites.
Using the International Phonetic Alphabet, Wajc would be spelled [vajts].

Still unsure? Check out this recording of Kira Radinsky:

Here's a subset of a Polish transcription table to explain how those letters are supposed to represent those sounds.

 Ww v as in "vat" Aa o as in "hot" Jj y as in "yes" Cc ts as in "bits"

And before you ask: no, I don't speak Polish. Here's a relevant meme by Krzysztof Onak: