News

I will be spending the Fall 2016 Semester at the Simons Institute for the Theory of Computing as part of the Algorithms and Uncertainty program.

I am broadly interested in algorithmic aspects of theoretical computer science. Recently I have been focusing on approximation and online algorithms.

Filter by type:

Sort by year:

A Faster Distributed Radio Broadcast Primitive (Extended Abstract)

Bernhard Haeupler, David Wajc
Conference PaperPODC 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 a 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.

Near-Optimum Online Ad Allocation for Targeted Advertising

Joseph (Seffi) Naor, David Wajc
Conference PaperEC 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
Conference PaperWWW (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
Conference PaperEC 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
Journal Paper Discrete 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.

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

At Carnegie Mellon

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: