Bernhard Haeupler

Yaowei Long

Thatchaphol Saranurak

CoRR, 2024

Fully Dynamic Consistent k-Center Clustering.

[BibT_eX]

[DOI]

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

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free.

[BibT_eX]

[DOI]

Greg Bodwin

Merav Parter

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

2023

Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts.

[BibT_eX]

[DOI]

Distributed Comput., December, 2023

Efficient Linear and Affine Codes for Correcting Insertions/Deletions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., June, 2023

Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps.

[BibT_eX]

[DOI]

CoRR, 2023

Fully Dynamic Consistent k-Center Clustering.

[BibT_eX]

[DOI]

CoRR, 2023

Parallel Greedy Spanners.

[BibT_eX]

[DOI]

Zihan Tan

CoRR, 2023

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.

[BibT_eX]

[DOI]

CoRR, 2023

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Simple Deterministic Distributed Low-Diameter Clustering.

[BibT_eX]

[DOI]

Václav Rozhon

Christoph Grunau

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.

[BibT_eX]

[DOI]

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

Sparse Semi-Oblivious Routing: Few Random Paths Suffice.

[BibT_eX]

[DOI]

Antti Roeyskoe

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

2022

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Circuits Resilient to Short-Circuit Errors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

A Cut-Matching Game for Constant-Hop Expanders.

[BibT_eX]

[DOI]

Jonas Hübotter

CoRR, 2022

Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms.

[BibT_eX]

[DOI]

CoRR, 2022

Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality.

[BibT_eX]

[DOI]

Harald Räcke

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates.

[BibT_eX]

[DOI]

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ1-Oblivious Routing.

[BibT_eX]

[DOI]

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

Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes.

[BibT_eX]

[DOI]

Proceedings of the IEEE Information Theory Workshop, 2022

Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Synchronization Strings and Codes for Insertions and Deletions - A Survey.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound.

[BibT_eX]

[DOI]

J. ACM, 2021

Low-Congestion shortcuts without embedding.

[BibT_eX]

[DOI]

Taisuke Izumi

Distributed Comput., 2021

Fast Algorithms for Hop-Constrained Flows and Moving Cuts.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

CoRR, 2021

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing.

[BibT_eX]

[DOI]

CoRR, 2021

Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries.

[BibT_eX]

[DOI]

CoRR, 2021

The Quest for Universally-Optimal Distributed Algorithms (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Distributed Computing, 2021

Universally-optimal distributed algorithms for known topologies.

[BibT_eX]

[DOI]

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

Tree embeddings for hop-constrained network design.

[BibT_eX]

[DOI]

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

Hop-constrained oblivious routing.

[BibT_eX]

[DOI]

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

A Time-Optimal Randomized Parallel Algorithm for MIS.

[BibT_eX]

[DOI]

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

Low-Congestion Shortcuts for Graphs Excluding Dense Minors.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Near-Optimal Schedules for Simultaneous Multicasts.

[BibT_eX]

[DOI]

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

2020

Rate-Distance Tradeoffs for List-Decodable Insertion-Deletion Codes.

[BibT_eX]

[DOI]

CoRR, 2020

Computation-Aware Data Aggregation.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Network Coding Gaps for Completion Times of Multiple Unicasts.

[BibT_eX]

[DOI]

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

Writeback-Aware Caching.

[BibT_eX]

[DOI]

Proceedings of the 1st Symposium on Algorithmic Principles of Computer Systems, 2020

2019

Optimally Resilient Codes for List-Decoding from Insertions and Deletions.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2019

Making asynchronous distributed computations robust to noise.

[BibT_eX]

[DOI]

Keren Censor-Hillel

Distributed Comput., 2019

Reliable communication over highly connected noisy networks.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Erasure Correction for Noisy Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Writeback-Aware Caching (Brief Announcement).

[BibT_eX]

[DOI]

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.

[BibT_eX]

[DOI]

Kuan Cheng

Xin Li

Ke Wu

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Optimal Strategies for Patrolling Fences.

[BibT_eX]

[DOI]

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

Optimal Document Exchange and New Codes for Insertions and Deletions.

[BibT_eX]

[DOI]

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

2018

Explicit Capacity Approaching Coding for Interactive Communication.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2018

Constant-Rate Coding for Multiparty Interactive Communication Is Impossible.

[BibT_eX]

[DOI]

J. ACM, 2018

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet.

[BibT_eX]

[DOI]

Gil Cohen

Leonard J. Schulman

Electron. Colloquium Comput. Complex., 2018

Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing.

[BibT_eX]

[DOI]

Aviad Rubinstein

CoRR, 2018

Algorithms for Noisy Broadcast under Erasures.

[BibT_eX]

[DOI]

Ofer Grossman

Sidhanth Mohanty

CoRR, 2018

A Computational Approach to Organizational Structure.

[BibT_eX]

[DOI]

CoRR, 2018

Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions.

[BibT_eX]

[DOI]

CoRR, 2018

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.

[BibT_eX]

[DOI]

Kuan Cheng

Xin Li

Ke Wu

CoRR, 2018

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

[BibT_eX]

[DOI]

CoRR, 2018

Faster Distributed Shortest Path Approximations via Shortcuts.

[BibT_eX]

[DOI]

Jason Li

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Allocate-On-Use Space Complexity of Shared-Memory Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Synchronization strings: explicit constructions, local decoding, and applications.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Optimal Gossip Algorithms for Exact and Approximate Quantile Computations.

[BibT_eX]

[DOI]

Jeet Mohapatra

Hsin-Hao Su

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

Minor Excluded Network Families Admit Fast Distributed Algorithms.

[BibT_eX]

[DOI]

Jason Li

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

Round- and Message-Optimal Distributed Graph Algorithms.

[BibT_eX]

[DOI]

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

Making Asynchronous Distributed Computations Robust to Channel Noise.

[BibT_eX]

[DOI]

Keren Censor-Hillel

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions.

[BibT_eX]

[DOI]

Ellen Vitercik

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

Synchronization Strings: List Decoding for Insertions and Deletions.

[BibT_eX]

[DOI]

Madhu Sudan

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

Algorithms for Noisy Broadcast with Erasures.

[BibT_eX]

[DOI]

Ofer Grossman

Sidhanth Mohanty

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

2017

Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs.

[BibT_eX]

[DOI]

David G. Harris

ACM Trans. Algorithms, 2017

Tight Bounds on Vertex Connectivity Under Sampling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Capacity of Interactive Communication over Erasure Channels and Channels with Feedback.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Rumor Spreading with No Dependence on Conductance.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication.

[BibT_eX]

[DOI]

Ofer Feinerman

Amos Korman

Distributed Comput., 2017

Broadcasting in Noisy Radio Networks.

[BibT_eX]

[DOI]

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

2016

SplayNet: Towards Locally Self-Adjusting Networks.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2016

Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback.

[BibT_eX]

[DOI]

Klim Efremenko

IEEE Trans. Inf. Theory, 2016

Discovery Through Gossip.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

Analyzing Network Coding (Gossip) Made Easy.

[BibT_eX]

[DOI]

J. ACM, 2016

Near-Optimal BFS-Tree Construction in Radio Networks.

[BibT_eX]

[DOI]

IEEE Commun. Lett., 2016

Bridging the Capacity Gap Between Interactive and One-Way Communication.

[BibT_eX]

[DOI]

Ameya Velingker

Electron. Colloquium Comput. Complex., 2016

Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs.

[BibT_eX]

[DOI]

Taisuke Izumi

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Faster Distributed Radio Broadcast Primitive: Extended Abstract.

[BibT_eX]

[DOI]

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

Distributed Algorithms for Planar Networks I: Planar Embedding.

[BibT_eX]

[DOI]

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

2015

Self-adjusting grid networks to minimize expected path length.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Rank-Balanced Trees.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2015

Network Coding Based Information Spreading in Dynamic Networks With Correlated Data.

[BibT_eX]

[DOI]

IEEE J. Sel. Areas Commun., 2015

Simple, Fast and Deterministic Gossip and Rumor Spreading.

[BibT_eX]

[DOI]

J. ACM, 2015

Towards Optimal Deterministic Coding for Interactive Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Randomized broadcast in radio networks with collision detection.

[BibT_eX]

[DOI]

Majid Khabbazian

Distributed Comput., 2015

Bounded-Contention Coding for the additive network model.

[BibT_eX]

[DOI]

Distributed Comput., 2015

Improved bounds and parallel algorithms for the Lovasz Local Lemma.

[BibT_eX]

[DOI]

David G. Harris

CoRR, 2015

Tight Bounds on Vertex Connectivity Under Vertex Sampling.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Distributed Resource Discovery in Sub-Logarithmic Time.

[BibT_eX]

[DOI]

Dahlia Malkhi

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

Communication with Partial Noiseless Feedback.

[BibT_eX]

[DOI]

Pritish Kamath

Ameya Velingker

Proceedings of the Approximation, 2015

2014

Consistent Weighted Sampling Made Fast, Small, and Easy.

[BibT_eX]

[DOI]

Mark S. Manasse

Kunal Talwar

CoRR, 2014

Fast Structuring of Radio Networks for Multi-Message Communications.

[BibT_eX]

[DOI]

CoRR, 2014

Optimal error rates for interactive coding I: adaptivity and other settings.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the Symposium on Theory of Computing, 2014

Broadcast Throughput in Radio Networks: Routing vs. Network Coding.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Optimal gossip with direct addressing.

[BibT_eX]

[DOI]

Dahlia Malkhi

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

Repeated deletion channels.

[BibT_eX]

[DOI]

Michael Mitzenmacher

Proceedings of the 2014 IEEE Information Theory Workshop, 2014

Interactive Channel Capacity Revisited.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Probabilistic methods for distributed information dissemination.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

PhD thesis, 2013

Deterministic Algorithms for the Lovász Local Lemma.

[BibT_eX]

[DOI]

Navin Goyal

SIAM J. Comput., 2013

Testing Simultaneous Planarity when the Common Graph is 2-Connected.

[BibT_eX]

[DOI]

Krishnam Raju Jampani

Anna Lubiw

J. Graph Algorithms Appl., 2013

Beeping a maximal independent set.

[BibT_eX]

[DOI]

Distributed Comput., 2013

A Bound on the Throughput of Radio Networks

[BibT_eX]

[DOI]

Majid Khabbazian

CoRR, 2013

Efficient and Noise-Resilient rumor-spreading in Large, Anonymous Populations.

[BibT_eX]

[DOI]

Ofer Feinerman

Amos Korman

CoRR, 2013

Fast Structuring of Radio Networks Large for Multi-message Communications.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 27th International Symposium, 2013

Near Optimal Leader Election in Multi-Hop Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Locally Self-Adjusting Tree Networks.

[BibT_eX]

[DOI]

Proceedings of the 27th IEEE International Symposium on Parallel and Distributed Processing, 2013

2012

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Tighter Worst-Case Bounds on Algebraic Gossip.

[BibT_eX]

[DOI]

IEEE Commun. Lett., 2012

The Complexity of Multi-Message Broadcast in Radio Networks with Known Topology

[BibT_eX]

[DOI]

Majid Khabbazian

CoRR, 2012

Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Lower Bounds on Information Dissemination in Dynamic Networks.

[BibT_eX]

[DOI]

Fabian Kuhn

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Bounds on Contention Management in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Bounded-Contention Coding for Wireless Networks in the High SNR Regime.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Network coded gossip with correlated data.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

2011

Rank-Pairing Heaps.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

New Constructive Aspects of the Lovász Local Lemma.

[BibT_eX]

[DOI]

Barna Saha

Aravind Srinivasan

J. ACM, 2011

Self-Adjusting Networks to Minimize Expected Path Length

[BibT_eX]

[DOI]

CoRR, 2011

Computing a Maximal Independent Set Using Beeps

[BibT_eX]

[DOI]

Alejandro Cornejo

Fabian Kuhn

CoRR, 2011

Optimality of Network Coding in Packet Networks

[BibT_eX]

[DOI]

Minji Kim

Muriel Médard

CoRR, 2011

Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive.

[BibT_eX]

[DOI]

William I. Gasarch

Electron. J. Comb., 2011

Online Stochastic Weighted Matching: Improved Approximation Algorithms.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Morteza Zadimoghaddam

Proceedings of the Internet and Network Economics - 7th International Workshop, 2011

Faster information dissemination in dynamic networks via network coding.

[BibT_eX]

[DOI]

David R. Karger

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Optimality of network coding with buffers.

[BibT_eX]

[DOI]

Minji Kim

Muriel Médard

Proceedings of the 2011 IEEE Information Theory Workshop, 2011

One packet suffices - Highly efficient packetized Network Coding With finite memory.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Muriel Médard

Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

2010

Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections

[BibT_eX]

[DOI]

Navin Goyal

CoRR, 2010

2009

Robust Regulatory Networks

[BibT_eX]

[DOI]

Arnab Bhattacharyya

CoRR, 2009

Heaps Simplified

[BibT_eX]

[DOI]

CoRR, 2009

2008

Finding a feasible flow in a strongly connected network.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Planarity Algorithms via PQ-Trees (Extended Abstract).

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2008

Incremental Topological Ordering and Strong Component Maintenance

[BibT_eX]

[DOI]