Publications:
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
[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
[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
[C29] Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc
STOC 2024
[C27] Simple and Optimal Online Bipartite Edge Coloring
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
SOSA 2024
[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
[C25] Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder, Joseph (Seffi) Naor, David Wajc
SODA 2023
[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
[C22] Beating the Folklore Algorithm for Dynamic Matching
Mohammad Roghani, Amin Saberi, David Wajc
ITCS 2022
[C19] Near-Optimal Schedules for Simultaneous Multicasts
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
ICALP 2021
[C18] Universally-Optimal Distributed Algorithms for Known Topologies
Bernhard Haeupler, David Wajc, Goran Zuzic
STOC 2021
[C11] Stochastic Online Metric Matching
Anupam Gupta, Guru Guruganesh, Binguhi Peng, David Wajc
ICALP 2019
[C10] Simplified and Space-Optimal Semi-Streaming (2+ε)-Approximate Matching
Mohsen Ghaffari, David Wajc
SOSA 2019
[C9] Round- and Message-Optimal Distributed Graph Algorithms
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
PODC 2018
[C7] Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
ICALP 2018
[C5] Approximation-Variance Tradeoffs in Facility Location Games
Ariel Procaccia, David Wajc, Hanrui Zhang
AAAI 2018
[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
[C2] You Will Get Mail! Predicting the Arrival of Future Email
Iftah Gamzu, Zohar Shay Karnin, Yoelle Maarek, David Wajc
WWW (Companion Volume) 2015
[C1] Best-Response Dynamics Out of Sync: Complexity and Characterization
Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc
EC 2013