Publications:
Publications:
[C36] Online Edge Coloring: Sharp Thresholds
Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc
FOCS 2025
[C35] Repairing Databases over Metric Spaces with Coincidence Constraints
Youri Kaminsky, Benny Kimelfeld, Ester Livshits & Felix Naumann, David Wajc
ICDT 2025
[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
[J6] Journal version in SICOMP, to appear
[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)
[J5] 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