| Publication | Date of Publication | Type |
|---|
| Near-optimal directed low-diameter decompositions | 2026-09-10 | Paper |
hop-constrained oblivious routing
SIAM Journal on Computing | 2026-09-02 | Paper |
| Graph decompositions and length-constrained expanders (invited talk) | 2026-08-31 | Paper |
| Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts | 2026-08-31 | Paper |
| Parallel, distributed, and quantum exact single-source shortest paths with negative edge weights | 2026-05-26 | Paper |
| Near-optimal schedules for simultaneous multicasts | 2026-05-12 | Paper |
| Deterministic low-diameter decompositions for weighted graphs and distributed and parallel applications | 2025-08-15 | Paper |
| Optimal document exchange and new codes for insertions and deletions | 2025-08-12 | Paper |
| Network coding gaps for completion times of multiple unicasts | 2025-08-12 | Paper |
| Interactive channel capacity revisited | 2025-08-05 | Paper |
| Optimal error rates for interactive coding. II: Efficiency and list decoding | 2025-08-05 | Paper |
| New constructive aspects of the Lovasz local lemma | 2025-04-29 | Paper |
| Fully dynamic consistent k-center clustering | 2024-11-28 | Paper |
| Fault-tolerant spanners against bounded-degree edge failures: linearly more faults, almost for free | 2024-11-28 | Paper |
| Universally-optimal distributed shortest paths and transshipment via graph-based _1-oblivious routing | 2024-07-19 | Paper |
| Improved distributed network decomposition, hitting sets, and spanners, via derandomization | 2024-05-14 | Paper |
| Interactive coding with small memory | 2024-05-14 | Paper |
| A simple deterministic distributed low-diameter clustering | 2024-05-14 | Paper |
| Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast | 2024-05-08 | Paper |
| Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances | 2024-05-08 | Paper |
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
| scientific article; zbMATH DE number 7788339 (Why is no real title available?) | 2024-01-15 | Paper |
| scientific article; zbMATH DE number 7788510 (Why is no real title available?) | 2024-01-15 | Paper |
Undirected (1+ <i>đ</i> )-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Circuits resilient to short-circuit errors
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | 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 |
| scientific article; zbMATH DE number 7774252 (Why is no real title available?) | 2023-12-08 | Paper |
Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
Distributed Computing | 2023-11-21 | Paper |
Tree embeddings for hop-constrained network design
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Hop-constrained oblivious routing
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Universally-optimal distributed algorithms for known topologies
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
SIAM Journal on Discrete Mathematics | 2023-06-14 | Paper |
Computation-Aware Data Aggregation.
(available as arXiv preprint) | 2023-02-03 | Paper |
| Erasure correction for noisy radio networks | 2023-02-03 | Paper |
Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
Journal of the ACM | 2022-12-08 | Paper |
| A Cut-Matching Game for Constant-Hop Expanders | 2022-11-21 | Paper |
Optimal strategies for patrolling fences
(available as arXiv preprint) | 2022-07-21 | Paper |
Faster distributed shortest path approximations via shortcuts
(available as arXiv preprint) | 2022-07-21 | Paper |
| Allocate-on-use space complexity of shared-memory algorithms | 2022-07-21 | Paper |
Optimally Resilient Codes for List-Decoding From Insertions and Deletions
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Synchronization strings: list decoding for insertions and deletions
(available as arXiv preprint) | 2021-07-28 | Paper |
Synchronization strings: channel simulations and interactive coding for insertions and deletions
(available as arXiv preprint) | 2021-07-28 | Paper |
Algorithms for noisy broadcast with erasures
(available as arXiv preprint) | 2021-07-28 | Paper |
Synchronization Strings and Codes for Insertions and DeletionsâA Survey
IEEE Transactions on Information Theory | 2021-07-23 | Paper |
| Making Asynchronous Distributed Computations Robust to Channel Noise | 2021-06-15 | Paper |
Low-congestion shortcuts without embedding
Distributed Computing | 2021-03-12 | Paper |
Optimally resilient codes for list-decoding from insertions and deletions
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
| Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes | 2020-09-28 | Paper |
Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Making asynchronous distributed computations robust to noise
Distributed Computing | 2019-11-27 | Paper |
Reliable communication over highly connected noisy networks
Distributed Computing | 2019-11-27 | Paper |
Synchronization strings: highly efficient deterministic constructions over small alphabets
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Minor excluded network families admit fast distributed algorithms
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Optimal gossip algorithms for exact and approximate quantile computations
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Round- and message-optimal distributed graph algorithms
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
Explicit binary tree codes with polylogarithmic size alphabet
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Synchronization strings: explicit constructions, local decoding, and applications
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | 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 |
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 |
Simple, fast and deterministic gossip and rumor spreading
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Parallel algorithms and concentration bounds for the LovĂĄsz local lemma via witness DAGs
ACM Transactions on Algorithms | 2018-11-12 | Paper |
Tight Bounds on Vertex Connectivity Under Sampling
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Rank-Balanced Trees
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Explicit Capacity Approaching Coding for Interactive Communication
IEEE Transactions on Information Theory | 2018-09-19 | Paper |
Optimal strategies for patrolling fences
(available as arXiv preprint) | 2018-09-18 | Paper |
| Near-optimal low-congestion shortcuts on bounded parameter graphs | 2018-08-16 | Paper |
Simple, fast and deterministic gossip and rumor spreading
Journal of the ACM | 2018-08-02 | Paper |
Analyzing network coding (gossip) made easy
Journal of the ACM | 2018-08-02 | Paper |
Constant-Rate Coding for Multiparty Interactive Communication Is Impossible
Journal of the ACM | 2018-08-02 | Paper |
Bridging the capacity gap between interactive and one-way communication
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Parallel algorithms and concentration bounds for the LovĂĄsz local lemma via witness-DAGs
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 |
Towards optimal deterministic coding for interactive communication
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Synchronization Strings: List Decoding for Insertions and Deletions
(available as arXiv preprint) | 2018-02-23 | Paper |
Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
Distributed Computing | 2018-01-17 | Paper |
Broadcasting in noisy radio networks
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 |
Capacity of interactive communication over erasure channels and channels with feedback
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Low-congestion shortcuts without embedding
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Constant-rate coding for multiparty interactive communication is impossible
Proceedings of the forty-eighth annual ACM symposium on Theory of 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 |
A Faster Distributed Radio Broadcast Primitive
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
Reliable communication over highly connected noisy networks
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing | 2017-09-29 | Paper |
| Communication with partial noiseless feedback | 2017-08-31 | Paper |
Capacity of interactive communication over erasure channels and channels with feedback
SIAM Journal on Computing | 2017-08-18 | Paper |
Synchronization strings: codes for insertions and deletions approaching the Singleton bound
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Maximal noise in interactive communication over erasure channels and channels with feedback
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
Rumor spreading with no dependence on conductance
SIAM Journal on Computing | 2017-02-15 | Paper |
Discovery through gossip
Random Structures & Algorithms | 2016-06-10 | Paper |
Distributed resource discovery in sub-logarithmic time
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 |
Bounded-contention coding for the additive network model
Distributed Computing | 2015-10-20 | Paper |
Faster information dissemination in dynamic networks via network coding
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-09-11 | Paper |
Optimal gossip with direct addressing
Proceedings of the 2014 ACM symposium on Principles of distributed computing | 2015-09-03 | Paper |
Breathe before speaking
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 |
Self-adjusting grid networks to minimize expected path length
Theoretical Computer Science | 2015-05-22 | Paper |
Randomized broadcast in radio networks with collision detection
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
Incremental cycle detection, topological ordering, and strong component maintenance
ACM Transactions on Algorithms | 2014-09-09 | Paper |
Analyzing network coding gossip made easy
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
| Deterministic algorithms for the LovĂĄsz local lemma | 2014-05-22 | Paper |
Global computation in a poorly connected world
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Deterministic algorithms for the LovĂĄsz local lemma
SIAM Journal on Computing | 2014-04-11 | Paper |
Beeping a maximal independent set
Distributed Computing | 2014-03-25 | Paper |
New constructive aspects of the LovĂĄsz local lemma
Journal of the ACM | 2014-02-17 | Paper |
Self-adjusting grid networks to minimize expected path length
Structural Information and Communication Complexity | 2013-12-17 | Paper |
Planarity algorithms via PQ-trees (extended abstract)
Electronic Notes in Discrete Mathematics | 2013-06-28 | Paper |
Testing simultaneous planarity when the common graph is 2-connected
Journal of Graph Algorithms and Applications | 2013-04-09 | Paper |
Bounds on contention management in radio networks
Lecture Notes in Computer Science | 2013-03-13 | Paper |
Bounded-contention coding for wireless networks in the high SNR regime
Lecture Notes in Computer Science | 2013-03-13 | Paper |
Lower bounds on information dissemination in dynamic 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 |
Rank-pairing heaps
SIAM Journal on Computing | 2012-03-15 | Paper |
Online stochastic weighted matching: improved approximation algorithms
Lecture Notes in Computer Science | 2011-12-05 | Paper |
Beeping a maximal independent set
Lecture Notes in Computer Science | 2011-10-28 | Paper |
Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive
The Electronic Journal of Combinatorics | 2011-06-01 | Paper |
Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive
The Electronic Journal of Combinatorics | 2011-06-01 | Paper |
Lower bounds on van der Waerden numbers: randomized- and deterministic-constructive
The Electronic Journal of Combinatorics | 2011-06-01 | Paper |
Testing simultaneous planarity when the common graph is 2-connected
Algorithms and Computation | 2010-12-09 | Paper |
Rank-Pairing Heaps
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Rank-Balanced Trees
Lecture Notes in Computer Science | 2009-10-20 | Paper |
Finding a feasible flow in a strongly connected network
Operations Research Letters | 2009-03-04 | Paper |
Faster Algorithms for Incremental Topological Ordering
Automata, Languages and Programming | 2008-08-28 | Paper |
