| Publication | Date of Publication | Type |
|---|
Local distributed rounding: generalized to MIS, matching, set cover, and beyond
ACM Transactions on Algorithms | 2025-11-03 | Paper |
| Work-efficient parallel derandomization. I: Chernoff-like concentrations via pairwise independence | 2025-08-15 | Paper |
| Local computation of maximal independent set | 2025-08-15 | Paper |
| Deterministic distributed vertex coloring: simpler, faster, and without network decomposition | 2025-08-13 | Paper |
| Conditional hardness results for massively parallel computation from distributed lower bounds | 2025-08-12 | Paper |
| On derandomizing local distributed algorithms | 2025-08-12 | Paper |
| Deterministic distributed edge-coloring via hypergraph maximal matching | 2025-08-06 | Paper |
| Optimal error rates for interactive coding. II: Efficiency and list decoding | 2025-08-05 | Paper |
| A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP | 2025-06-13 | Paper |
Near-optimal distributed dominating set in bounded arboricity graphs
Distributed Computing | 2025-01-08 | Paper |
| A distributed palette sparsification theorem | 2024-11-28 | Paper |
| Simplified and space-optimal semi-streaming (2+)-approximate matching | 2024-08-26 | Paper |
| Improved distributed network decomposition, hitting sets, and spanners, via derandomization | 2024-05-14 | Paper |
| A nearly time-optimal distributed approximation of minimum cost k-edge-connected spanning subgraph | 2024-05-14 | Paper |
| Local distributed rounding: generalized to MIS, matching, set cover, and beyond | 2024-05-14 | Paper |
| Faster deterministic distributed MIS and approximate matching | 2024-05-08 | Paper |
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Strong-Diameter Network Decomposition
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Node and Edge Averaged Complexities of Local Graph Problems
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Universally-Optimal Distributed Exact Min-Cut
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Distributed MIS with Low Energy and Time Complexities
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
A Near-Optimal Deterministic Distributed Synchronizer
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
SIAM Journal on Computing | 2024-03-19 | Paper |
| scientific article; zbMATH DE number 7788510 (Why is no real title available?) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788511 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Node and edge averaged complexities of local graph problems
Distributed Computing | 2023-11-21 | Paper |
Hop-constrained oblivious routing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Improved MPC algorithms for MIS, matching, and coloring on trees and beyond | 2023-11-02 | Paper |
| Simple and near-optimal distributed coloring for sparse graphs | 2023-02-03 | Paper |
| Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy | 2023-02-03 | Paper |
| Near-optimal distributed DFS in planar graphs | 2023-02-03 | Paper |
| Distributed algorithms for low stretch spanning trees | 2023-02-03 | Paper |
| Improved distributed degree splitting and edge coloring | 2023-02-03 | Paper |
| Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond | 2023-02-03 | Paper |
| A Cut-Matching Game for Constant-Hop Expanders | 2022-11-21 | Paper |
Network Decomposition and Distributed Derandomization (Invited Paper)
Structural Information and Communication Complexity | 2022-09-01 | Paper |
| Distributed MST and broadcast with fewer messages, and faster gossiping | 2022-07-21 | Paper |
| Derandomizing distributed algorithms with small messages: spanners and dominating set | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561283 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
| Distributed set cover approximation: primal-dual with optimal locality | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561278 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7561635 (Why is no real title available?) | 2022-07-21 | Paper |
Improved distributed \(\Delta\)-coloring
Distributed Computing | 2021-09-06 | Paper |
A tight analysis of the parallel undecided-state dynamics with two colors
(available as arXiv preprint) | 2021-08-04 | Paper |
Massively Parallel Algorithms for Minimum Cut
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
On the Complexity of Distributed Splitting Problems
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
On the Use of Randomness in Local Distributed Graph Algorithms
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Polylogarithmic-time deterministic network decomposition and distributed derandomization
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Improved distributed degree splitting and edge coloring
Distributed Computing | 2020-06-15 | Paper |
Improved distributed degree splitting and edge coloring
Distributed Computing | 2020-06-15 | Paper |
Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Distributed Maximal Independent Set using Small Messages
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Congested Clique Algorithms for the Minimum Cut Problem
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Improved massively parallel computation algorithms for MIS, matching, and vertex cover
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Improved distributed delta-coloring
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Improved distributed algorithms for exact shortest paths
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Deterministic distributed edge-coloring with fewer colors
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
(available as arXiv preprint) | 2019-07-25 | Paper |
Broadcast throughput in radio networks: routing vs. network coding
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
A new perspective on vertex connectivity
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Near optimal leader election in multi-hop radio networks
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Near-optimal distributed maximum flow
SIAM Journal on Computing | 2018-12-05 | Paper |
Tight Bounds on Vertex Connectivity Under Sampling
ACM Transactions on Algorithms | 2018-11-05 | Paper |
How to discreetly spread a rumor in a crowd
(available as arXiv preprint) | 2018-08-16 | Paper |
An Improved Distributed Algorithm for Maximal Independent Set
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Distributed degree splitting, edge coloring, and orientations
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Random contractions and sampling for hypergraph and hedge connectivity
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Leader election in unreliable radio networks | 2017-12-19 | Paper |
Distributed MST and routing in almost mixing time
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Distributed approximation of maximum independent set and maximum matching
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Distributed MIS via all-to-all communication
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Tight bounds on vertex connectivity under vertex sampling
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
A polylogarithmic gossip algorithm for plurality consensus
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Distributed algorithms for planar networks. I: Planar embedding
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
MST in log-star rounds of congested clique
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
On the complexity of local distributed graph problems
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Near-optimal scheduling of distributed algorithms
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
Near-optimal distributed maximum flow (extended abstract)
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
Distributed house-hunting in ant colonies
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing | 2016-03-23 | Paper |
Randomized broadcast in radio networks with collision detection
Distributed Computing | 2016-01-06 | Paper |
Randomized broadcast in radio networks with collision detection
Distributed Computing | 2016-01-06 | Paper |
Distributed Broadcast Revisited: Towards Universal Optimality
Automata, Languages, and Programming | 2015-11-04 | Paper |
Multi-message broadcast with abstract MAC layers and unreliable links
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Distributed connectivity decomposition
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Optimal error rates for interactive coding. I: Adaptivity and other settings
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Maximal independent sets in multichannel radio networks
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
The cost of radio network broadcast for different models of unreliable links
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
Randomized broadcast in radio networks with collision detection
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
Distributed minimum cut approximation
Lecture Notes in Computer Science | 2014-09-29 | Paper |
Near-optimal distributed approximation of minimum-weight connected dominating set
Automata, Languages, and Programming | 2014-07-01 | Paper |
Bounds on contention management in radio networks
Lecture Notes in Computer Science | 2013-03-13 | Paper |
Bounds on contention management in radio networks
Lecture Notes in Computer Science | 2013-03-13 | Paper |
Leader election using loneliness detection
Distributed Computing | 2013-02-04 | Paper |
Leader election using loneliness detection
Lecture Notes in Computer Science | 2011-10-28 | Paper |
