David Wajc

Orcid: 0000-0003-1896-2948

According to our database1, David Wajc authored at least 37 papers between 2011 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Online Edge Coloring is (Nearly) as Easy as Offline.
CoRR, 2024

2023
Combinatorial Stationary Prophet Inequalities.
CoRR, 2023

Simple and Asymptotically Optimal Online Bipartite Edge Coloring.
CoRR, 2023

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

Online Dependent Rounding Schemes.
CoRR, 2023

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility).
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy.
Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

The Stationary Prophet Inequality Problem.
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.
Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021
Matching Theory Under Uncertainty.
PhD thesis, 2021

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

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

Universally-optimal distributed algorithms for known topologies.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Streaming Submodular Matching Meets the Primal-Dual Method.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Edge Coloring Algorithms via the Nibble Method.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities.
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

The Greedy Algorithm Is not Optimal for On-Line Edge Coloring.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Near-Optimal Schedules for Simultaneous Multicasts.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020
Rounding dynamic matchings against an adaptive adversary.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Network Coding Gaps for Completion Times of Multiple Unicasts.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Stochastic Online Metric Matching.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Online Matching with General Arrivals.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Tight Bounds for Online Edge Coloring.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Near-Optimum Online Ad Allocation for Targeted Advertising.
ACM Trans. Economics and Comput., 2018

Round- and Message-Optimal Distributed Part-Wise Aggregation.
CoRR, 2018

Randomized Online Matching in Regular Graphs.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Round- and Message-Optimal Distributed Graph Algorithms.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Fully-Dynamic Bin Packing with Little Repacking.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Approximation-Variance Tradeoffs in Facility Location Games.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017
Fully-Dynamic Bin Packing with Limited Repacking.
CoRR, 2017

2016
A Faster Distributed Radio Broadcast Primitive: Extended Abstract.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015
You Will Get Mail!Predicting the Arrival of Future Email.
Proceedings of the 24th International Conference on World Wide Web Companion, 2015

2013
Best-response dynamics out of sync: complexity and characterization.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2011
On the complexity of vertex-coloring edge-weightings.
Discret. Math. Theor. Comput. Sci., 2011


  Loading...