Publications:

[C30]  Online Edge Coloring is (Nearly) as Easy as Offline

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
STOC 2024

PDF

[C29]  Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
 Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
STOC 2024

PDF

[C28]  Combinatorial Stationary Prophet Inequalities

Neel Patel, David Wajc
SODA 2024

PDF

[C27]  Simple and Optimal Online Bipartite Edge Coloring

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
SOSA 2024

PDF

[C26]  Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc
SODA 2023 Best paper award

PDF

[C25]  Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)

Niv Buchbinder, Joseph (Seffi) Naor, David Wajc
SODA 2023

PDF

[C24]  Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc
EC 2022

[J4] Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Math of OR (To appear)

PDF

[C23]  The Stationary Prophet Inequality Problem

Kristen Kessel, Amin Saberi, Ali Shameli, David Wajc
EC 2022

PDF  Video

[C22]  Beating the Folklore Algorithm for Dynamic Matching

Mohammad Roghani, Amin Saberi, David Wajc
ITCS 2022

PDF

[C21]  Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

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

[J3]  Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities

Math of OR (To appear)

PDF  Video

[C20]  The Greedy Algorithm is not optimal for On-Line Edge Coloring

Amin Saberi, David Wajc
ICALP 2021

PDF  Video

[C19]  Near-Optimal Schedules for Simultaneous Multicasts

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

PDF

[C18]  Universally-Optimal Distributed Algorithms for Known Topologies

Bernhard Haeupler, David Wajc, Goran Zuzic
STOC 2021

PDF

[C17]  Streaming Submodular Matching Meets the Primal-Dual Method

Roie Levin, David Wajc
SODA 2021

PDF

[C16]  Online Algorithms for Edge Coloring via the Nibble Method

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
SODA 2021

PDF  Video

[C15]  Network Coding Gaps for Completion Time of Multiple Unicasts

Bernhard Haeupler, David Wajc, Goran Zuzic
FOCS 2020

PDF  Video  

[C14]  Rounding Dynamic Matchings Against an Adaptive Adversary

David Wajc
STOC 2020

PDF  Video

[C13]  Online Matching with General Arrivals

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

PDF  Video

[C12]  Tight Bounds for Online Edge Coloring

Ilan Reuven Cohen, Binghui Peng, David Wajc
FOCS 2019 Invited to Highlights of Algorithms (HALG) 2020

PDF  Video

[C11]  Stochastic Online Metric Matching

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

PDF

[C10]  Simplified and Space-Optimal Semi-Streaming (2+ε)-Approximate Matching

Mohsen Ghaffari, David Wajc
SOSA 2019

PDF

[C9]  Round- and Message-Optimal Distributed Graph Algorithms

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

PDF

[C8]  Fully-Dynamic Bin Packing with Limited Repacking

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

PDF  Video

[C7]  Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

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

PDF

[C6]  Randomized Online Matching in Regular Graphs

Ilan R. Cohen, David Wajc
SODA 2018

PDF  Video

[C5]  Approximation-Variance Tradeoffs in Facility Location Games

Ariel Procaccia, David Wajc, Hanrui Zhang
AAAI 2018

PDF

[C4]  A Faster Distributed Radio Broadcast Primitive (Extended Abstract)

Bernhard Haeupler, David Wajc
PODC 2016

PDF  Video

[C3]  Near-Optimum Online Ad Allocation for Targeted Advertising

Joseph (Seffi) Naor, David Wajc
EC 2015 Invited to Special Issue

[J2]  Near-Optimum Online Ad Allocation for Targeted Advertising

TEAC 2018

PDF

[C2]  You Will Get Mail! Predicting the Arrival of Future Email

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

PDF

[C1]  Best-Response Dynamics Out of Sync: Complexity and Characterization

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

PDF

[J1]  On the complexity of vertex-coloring edge-weightings

Andrzej Dudek, David Wajc
DMTCS 2011

PDF