David Wajc

According to our database, David Wajc authored at least 42 papers between 2011 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.

Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc

J. ACM, October, 2024

Online Matching: A Brief Survey.

Zhiyi Huang, Zhihao Gavin Tang, David Wajc

SIGecom Exch., 2024

Improved Online Contention Resolution for Matchings and Applications to the Gig Economy.

Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc

Math. Oper. Res., 2024

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities.

Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc

Math. Oper. Res., 2024

Repairing Databases over Metric Spaces with Coincidence Constraints.

Youri Kaminsky, Benny Kimelfeld, Ester Livshits, Felix Naumann, David Wajc

CoRR, 2024

Deterministic Online Bipartite Edge Coloring.

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc

CoRR, 2024

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling.

Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc

CoRR, 2024

Online Edge Coloring Is (Nearly) as Easy as Offline.

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs.

Sayan Bhattacharya, Peter Kiss, Aaron Sidford, David Wajc

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Simple and Asymptotically Optimal Online Bipartite Edge Coloring.

Joakim Blikstad, Ola Svensson, Radu Vintan, David Wajc

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Combinatorial Stationary Prophet Inequalities.

Neel Patel, David Wajc

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

The Average-Value Allocation Problem.

Kshipra Bhawalkar, Zhe Feng, Anupam Gupta, Aranyak Mehta, David Wajc, Di Wang

Proceedings of the Approximation, 2024

2023

Online Dependent Rounding Schemes.

Joseph Naor, Aravind Srinivasan, David Wajc

CoRR, 2023

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility).

Niv Buchbinder, Joseph (Seffi) Naor, David Wajc

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

The Stationary Prophet Inequality Problem.

Kristen Kessel, Ali Shameli, Amin Saberi, David Wajc

Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Beating the Folklore Algorithm for Dynamic Matching.

Mohammad Roghani, Amin Saberi, David Wajc

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Matching Theory Under Uncertainty.

David Wajc

PhD thesis, 2021

A Randomness Threshold for Online Bipartite Matching, via Lossless Online Rounding.

Niv Buchbinder, Joseph Naor, David Wajc

CoRR, 2021

The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring.

Amin Saberi, David Wajc

CoRR, 2021

Universally-optimal distributed algorithms for known topologies.

Bernhard Haeupler, David Wajc, Goran Zuzic

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Streaming Submodular Matching Meets the Primal-Dual Method.

Roie Levin, David Wajc

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Edge Coloring Algorithms via the Nibble Method.

Sayan Bhattacharya, Fabrizio Grandoni, David Wajc

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Greedy Algorithm Is not Optimal for On-Line Edge Coloring.

Amin Saberi, David Wajc

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Near-Optimal Schedules for Simultaneous Multicasts.

Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Rounding dynamic matchings against an adaptive adversary.

David Wajc

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Network Coding Gaps for Completion Times of Multiple Unicasts.

Bernhard Haeupler, David Wajc, Goran Zuzic

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching.

Mohsen Ghaffari, David Wajc

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Stochastic Online Metric Matching.

Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Online Matching with General Arrivals.

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

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Tight Bounds for Online Edge Coloring.

Ilan Reuven Cohen, Binghui Peng, David Wajc

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Near-Optimum Online Ad Allocation for Targeted Advertising.

Joseph (Seffi) Naor, David Wajc

ACM Trans. Economics and Comput., 2018

Round- and Message-Optimal Distributed Part-Wise Aggregation.

Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

CoRR, 2018

Randomized Online Matching in Regular Graphs.

Ilan Reuven Cohen, David Wajc

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Round- and Message-Optimal Distributed Graph Algorithms.

Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Fully-Dynamic Bin Packing with Little Repacking.

Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.

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

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Approximation-Variance Tradeoffs in Facility Location Games.

Ariel D. Procaccia, David Wajc, Hanrui Zhang

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Fully-Dynamic Bin Packing with Limited Repacking.

Anupam Gupta, Guru Guruganesh, Amit Kumar, David Wajc

CoRR, 2017

2016

A Faster Distributed Radio Broadcast Primitive: Extended Abstract.

Bernhard Haeupler, David Wajc

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

You Will Get Mail!Predicting the Arrival of Future Email.

Iftah Gamzu, Zohar Shay Karnin, Yoelle Maarek, David Wajc

Proceedings of the 24th International Conference on World Wide Web Companion, 2015

2013

Best-response dynamics out of sync: complexity and characterization.

Roee Engelberg, Alex Fabrikant, Michael Schapira, David Wajc

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2011

On the complexity of vertex-coloring edge-weightings.

Andrzej Dudek, David Wajc

Discret. Math. Theor. Comput. Sci., 2011