
UniversallyOptimal Distributed Algorithms for Known Topologies
Many distributed optimization algorithms achieve existentiallyoptimal r...
read it

Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Embeddings of graphs into distributions of trees that preserve distances...
read it

Synchronization Strings and Codes for Insertions and Deletions – a Survey
Already in the 1960s, Levenshtein and others studied errorcorrecting co...
read it

HopConstrained Oblivious Routing
We prove the existence of an oblivious routing scheme that is poly(log n...
read it

Tree Embeddings for HopConstrained Network Design
Network design problems aim to compute lowcost structures such as route...
read it

RateDistance Tradeoffs for ListDecodable InsertionDeletion Codes
This paper presents general bounds on the highest achievable rate for li...
read it

LowCongestion Shortcuts for Graphs Excluding Dense Minors
We prove that any nnode graph G with diameter D admits shortcuts with c...
read it

Efficient Linear and Affine Codes for Correcting Insertions/Deletions
This paper studies linear and affine errorcorrecting codes for correcti...
read it

NearOptimal Schedules for Simultaneous Multicasts
We study the storeandforward packet routing problem for simultaneous m...
read it

Optimally Resilient Codes for ListDecoding from Insertions and Deletions
We give a complete answer to the following basic question: "What is the ...
read it

Network Coding Gaps for Completion Times of Multiple Unicasts
Arguably the most common network communication problem is multipleunica...
read it

NearLinear Time InsertionDeletion Codes and (1+ε)Approximating Edit Distance via Indexing
We introduce fastdecodable indexing schemes for edit distance which can...
read it

Optimal strategies for patrolling fences
A classical multiagent fence patrolling problem asks: What is the maxim...
read it

Algorithms for Noisy Broadcast under Erasures
The noisy broadcast model was first studied in [Gallager, TranInf'88] wh...
read it

A Computational Approach to Organizational Structure
An organizational structure defines how an organization arranges and man...
read it

Coding for Interactive Communication with Small Memory and Applications to Robust Circuits
Classically, coding theory has been concerned with the problem of transm...
read it

Erasure Correction for Noisy Radio Networks
The radio network model is a wellstudied abstraction for modeling wirel...
read it

Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions
This paper gives a communicationoptimal document exchange protocol and ...
read it

Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Synchronization strings are recently introduced by Haeupler and Shahrasb...
read it

Synchronization Strings: List Decoding for Insertions and Deletions
We study codes that are listdecodable under insertions and deletions. S...
read it

Faster Distributed Shortest Path Approximations via Shortcuts
A long series of recent results and breakthroughs have led to faster and...
read it

Minor Excluded Network Families Admit Fast Distributed Algorithms
Distributed network optimization algorithms, such as minimum spanning tr...
read it

Round and MessageOptimal Distributed Graph Algorithms
Distributed graph algorithms that separately optimize for either the num...
read it

Round and MessageOptimal Distributed PartWise Aggregation
Distributed graph algorithms that separately optimize for either the num...
read it

Optimal Gossip Algorithms for Exact and Approximate Quantile Computations
This paper gives drastically faster gossip algorithms to compute exact a...
read it
Bernhard Haeupler
is this you? claim profile