Publications:

[C34]  New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
 Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc
SODA 2025
PDF

[C33]  Online Dependent Rounding Schemes for Bipartite Matchings, with Applications

Joseph (Seffi) Naor, Aravind Srinivasan, David Wajc
SODA 2025

PDF

[C32]  Deterministic Online Bipartite Edge Coloring

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
SODA 2025
PDF

[C31]  The Average-Value Allocation Problem
 Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, Di Wang, David Wajc
APPROX 2024 Invited to ToC Special Issue

PDF

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

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
STOC 2024 Invited to SICOMP Special Issue

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

Invited to Special Issue of TALG (declined in favor of J.ACM)

Journal version in J.ACM  2024

Invited talk at Highlights of Algorithms (HALG) 2024

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
Journal version in Math of OR 2024

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

Journal version in Math of OR 2024

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 talk at 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 TEAC Special Issue

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

Journal version in 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