Bernhard Haeupler

260 papers A* 71A 21B 10Journal 147Unranked 10

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations. ITCS Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi, Ulysse Schaller
2026	J	`jnl`	Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness. CoRR Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang
2026	—	`conf`	Reducing Shortcut and Hopset Constructions to Shallow Graphs. SOSA Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
2026	—	`conf`	Simple Length-Constrained Expander Decompositions. SOSA Greg Bodwin, Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan
2025	A*	`conf`	A Cut-Matching Game for Constant-Hop Expanders. SODA Bernhard Haeupler, Jonas Hübotter, Mohsen Ghaffari
2025	—	`conf`	A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path. SOSA Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, Aurelio L. Sulser
2025	J	`jnl`	Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations. CoRR Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi, Ulysse Schaller
2025	—	`conf`	Bidirectional Dijkstra's Algorithm is Instance-Optimal. SOSA Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2025	J	`jnl`	Clustering with Label Consistency. CoRR Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson
2025	J	`jnl`	Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric. CoRR Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
2025	J	`jnl`	Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers. CoRR Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
2025	A*	`conf`	Fast and Simple Sorting Using Partial Information. SODA Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2025	A	`conf`	Graph Decompositions and Length-Constrained Expanders (Invited Talk). ESA Bernhard Haeupler
2025	A	`conf`	Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts. ESA Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
2025	J	`jnl`	Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts. CoRR Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
2025	J	`jnl`	Maintaining Routing Structures under Deletions via Self-Pruning. CoRR Bernhard Haeupler, Antti Roeyskoe
2025	A*	`conf`	Near-Optimal Directed Low-Diameter Decompositions. ICALP Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov
2025	J	`jnl`	Near-Optimal Directed Low-Diameter Decompositions. CoRR Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov
2025	A*	`conf`	Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and Work. FOCS Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
2025	J	`jnl`	Parallel (1+ε)-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work. CoRR Bernhard Haeupler, Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak, Shengzhe Wang
2025	J	`jnl`	Reducing Shortcut and Hopset Constructions to Shallow Graphs. CoRR Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
2025	J	`jnl`	Reviving Thorup's Shortcut Conjecture. CoRR Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
2025	J	`jnl`	Simple Length-Constrained Expander Decompositions. CoRR Greg Bodwin, Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan
2025	J	`jnl`	Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation. CoRR Bernhard Haeupler, Richard Hladík, Shengzhe Wang, Zhijun Zhang
2024	J	`jnl`	A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths. CoRR Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, Aurelio L. Sulser
2024	J	`jnl`	Bidirectional Dijkstra's Algorithm is Instance-Optimal. CoRR Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2024	A*	`conf`	Dynamic Deterministic Constant-Approximate Distance Oracles with n FOCS Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
2024	J	`jnl`	Dynamic Deterministic Constant-Approximate Distance Oracles with n CoRR Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
2024	J	`jnl`	Fast and Simple Sorting Using Partial Information. CoRR Bernhard Haeupler, Richard Hladík, John Iacono, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2024	A*	`conf`	Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. SODA Greg Bodwin, Bernhard Haeupler, Merav Parter
2024	A*	`conf`	Fully Dynamic Consistent SODA Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, Václav Rozhon
2024	J	`jnl`	Interactive Coding with Small Memory and Improved Rate. CoRR Dorsa Fathollahi, Bernhard Haeupler, Nicolas Resch, Mary Wootters
2024	J	`jnl`	Low-Step Multi-Commodity Flow Emulators. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak
2024	A*	`conf`	Low-Step Multi-commodity Flow Emulators. STOC Bernhard Haeupler, D. Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak
2024	A*	`conf`	New Structures and Algorithms for Length-Constrained Expander Decompositions. FOCS Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan
2024	J	`jnl`	New Structures and Algorithms for Length-Constrained Expander Decompositions. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan
2024	A	`conf`	Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights. ESA Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2024	A*	`conf`	Polylog-Competitive Deterministic Local Routing and Scheduling. STOC Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe, Cliff Stein, Goran Zuzic
2024	J	`jnl`	Polylog-Competitive Deterministic Local Routing and Scheduling. CoRR Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe, Cliff Stein, Goran Zuzic
2024	A*	`conf`	Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps. FOCS Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2023	—	`conf`	A Simple Deterministic Distributed Low-Diameter Clustering. SOSA Václav Rozhon, Bernhard Haeupler, Christoph Grunau
2023	J	`jnl`	Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts. Distributed Comput. Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis
2023	J	`jnl`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SIAM J. Discret. Math. Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2023	J	`jnl`	Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free. CoRR Greg Bodwin, Bernhard Haeupler, Merav Parter
2023	J	`jnl`	Fully Dynamic Consistent k-Center Clustering. CoRR Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Václav Rozhon, Rajesh Jayaram
2023	A*	`conf`	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. SODA Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2023	A*	`conf`	Interactive Coding with Small Memory. SODA Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2023	A*	`conf`	Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and Fast. STOC Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak
2023	A*	`conf`	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. STOC Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic
2023	J	`jnl`	Parallel Greedy Spanners. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan
2023	J	`jnl`	Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights. CoRR Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Danupon Nanongkai, Hsin-Hao Su
2023	A*	`conf`	Sparse Semi-Oblivious Routing: Few Random Paths Suffice. PODC Goran Zuzic, Bernhard Haeupler, Antti Roeyskoe
2023	J	`jnl`	Sparse Semi-Oblivious Routing: Few Random Paths Suffice. CoRR Goran Zuzic, Bernhard Haeupler, Antti Roeyskoe
2023	J	`jnl`	Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps. CoRR Bernhard Haeupler, Richard Hladík, Václav Rozhon, Robert E. Tarjan, Jakub Tetek
2022	J	`jnl`	A Cut-Matching Game for Constant-Hop Expanders. CoRR Bernhard Haeupler, Jonas Hübotter, Mohsen Ghaffari
2022	J	`jnl`	A Simple Deterministic Distributed Low-Diameter Clustering. CoRR Václav Rozhon, Bernhard Haeupler, Christoph Grunau
2022	A	`conf`	Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts. DISC Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis
2022	A*	`conf`	Brief Announcement: Almost Universally Optimal Distributed Laplacian Solver. PODC Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis
2022	J	`jnl`	Circuits Resilient to Short-Circuit Errors. Electron. Colloquium Comput. Complex. Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
2022	A*	`conf`	Circuits resilient to short-circuit errors. STOC Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2022	B	`conf`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. SPAA Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. CoRR Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	A*	`conf`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler
2022	J	`jnl`	Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau
2022	A*	`conf`	Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. STOC Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari
2022	J	`jnl`	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. CoRR Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
2022	J	`jnl`	Interactive Coding with Small Memory. Electron. Colloquium Comput. Complex. Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai
2022	J	`jnl`	Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. CoRR Václav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic
2022	B	`conf`	Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes. ITW Bernhard Haeupler, Amirbehshad Shahrasbi
2022	A*	`conf`	Undirected (1+ STOC Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li
2022	J	`jnl`	Undirected (1+ε)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms. CoRR Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li
2022	A*	`conf`	Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based ℓ SODA Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun
2021	A*	`conf`	A Time-Optimal Randomized Parallel Algorithm for MIS. SODA Mohsen Ghaffari, Bernhard Haeupler
2021	J	`jnl`	Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2021	A*	`conf`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SODA Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2021	J	`jnl`	Fast Algorithms for Hop-Constrained Flows and Moving Cuts. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Thatchaphol Saranurak
2021	A*	`conf`	Hop-constrained oblivious routing. STOC Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic
2021	A*	`conf`	Low-Congestion Shortcuts for Graphs Excluding Dense Minors. PODC Mohsen Ghaffari, Bernhard Haeupler
2021	J	`jnl`	Low-Congestion shortcuts without embedding. Distributed Comput. Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
2021	A*	`conf`	Near-Optimal Schedules for Simultaneous Multicasts. ICALP Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
2021	J	`jnl`	Optimally Resilient Codes for List-Decoding From Insertions and Deletions. IEEE Trans. Inf. Theory Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2021	J	`jnl`	Synchronization Strings and Codes for Insertions and Deletions - A Survey. IEEE Trans. Inf. Theory Bernhard Haeupler, Amirbehshad Shahrasbi
2021	J	`jnl`	Synchronization Strings and Codes for Insertions and Deletions - a Survey. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi
2021	J	`jnl`	Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound. J. ACM Bernhard Haeupler, Amirbehshad Shahrasbi
2021	A	`conf`	The Quest for Universally-Optimal Distributed Algorithms (Invited Talk). DISC Bernhard Haeupler
2021	A*	`conf`	Tree embeddings for hop-constrained network design. STOC Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2021	J	`jnl`	Universally-Optimal Distributed Algorithms for Known Topologies. CoRR Bernhard Haeupler, David Wajc, Goran Zuzic
2021	J	`jnl`	Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing. CoRR Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun
2021	A*	`conf`	Universally-optimal distributed algorithms for known topologies. STOC Bernhard Haeupler, David Wajc, Goran Zuzic
2020	A	`conf`	Computation-Aware Data Aggregation. ITCS Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia
2020	J	`jnl`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. CoRR Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2020	J	`jnl`	Hop-Constrained Oblivious Routing. CoRR Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic
2020	J	`jnl`	Low-Congestion Shortcuts for Graphs Excluding Dense Minors. CoRR Mohsen Ghaffari, Bernhard Haeupler
2020	J	`jnl`	Near-Optimal Schedules for Simultaneous Multicasts. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
2020	A*	`conf`	Network Coding Gaps for Completion Times of Multiple Unicasts. FOCS Bernhard Haeupler, David Wajc, Goran Zuzic
2020	A*	`conf`	Optimally resilient codes for list-decoding from insertions and deletions. STOC Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2020	J	`jnl`	Rate-Distance Tradeoffs for List-Decodable Insertion-Deletion Codes. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi
2020	J	`jnl`	Tree Embeddings for Hop-Constrained Network Design. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2020	—	`conf`	Writeback-Aware Caching. APOCS Nathan Beckmann, Phillip B. Gibbons, Bernhard Haeupler, Charles McGuffey
2019	A	`conf`	Erasure Correction for Noisy Radio Networks. DISC Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2019	J	`jnl`	Making asynchronous distributed computations robust to noise. Distributed Comput. Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
2019	A*	`conf`	Near-linear time insertion-deletion codes and (1+ STOC Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
2019	J	`jnl`	Network Coding Gaps for Completion Times of Multiple Unicasts. CoRR Bernhard Haeupler, David Wajc, Goran Zuzic
2019	A*	`conf`	Optimal Document Exchange and New Codes for Insertions and Deletions. FOCS Bernhard Haeupler
2019	A*	`conf`	Optimal Strategies for Patrolling Fences. ICALP Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister
2019	J	`jnl`	Optimally Resilient Codes for List-Decoding from Insertions and Deletions. CoRR Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2019	J	`jnl`	Optimally Resilient Codes for List-Decoding from Insertions and Deletions. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2019	J	`jnl`	Reliable communication over highly connected noisy networks. Distributed Comput. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2019	A*	`conf`	Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets. SODA Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu
2019	B	`conf`	Writeback-Aware Caching (Brief Announcement). SPAA Nathan Beckmann, Phillip B. Gibbons, Bernhard Haeupler, Charles McGuffey
2018	J	`jnl`	A Computational Approach to Organizational Structure. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia
2018	J	`jnl`	Algorithms for Noisy Broadcast under Erasures. CoRR Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty
2018	A*	`conf`	Algorithms for Noisy Broadcast with Erasures. ICALP Ofer Grossman, Bernhard Haeupler, Sidhanth Mohanty
2018	A	`conf`	Allocate-On-Use Space Complexity of Shared-Memory Algorithms. DISC James Aspnes, Bernhard Haeupler, Alexander Tong, Philipp Woelfel
2018	J	`jnl`	Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2018	J	`jnl`	Erasure Correction for Noisy Radio Networks. CoRR Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2018	J	`jnl`	Explicit Binary Tree Codes with Polylogarithmic Size Alphabet. Electron. Colloquium Comput. Complex. Gil Cohen, Bernhard Haeupler, Leonard J. Schulman
2018	J	`jnl`	Explicit Capacity Approaching Coding for Interactive Communication. IEEE Trans. Inf. Theory Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2018	A*	`conf`	Explicit binary tree codes with polylogarithmic size alphabet. STOC Gil Cohen, Bernhard Haeupler, Leonard J. Schulman
2018	A	`conf`	Faster Distributed Shortest Path Approximations via Shortcuts. DISC Bernhard Haeupler, Jason Li
2018	J	`jnl`	Faster Distributed Shortest Path Approximations via Shortcuts. CoRR Bernhard Haeupler, Jason Li
2018	A	`conf`	Making Asynchronous Distributed Computations Robust to Channel Noise. ITCS Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
2018	A*	`conf`	Minor Excluded Network Families Admit Fast Distributed Algorithms. PODC Bernhard Haeupler, Jason Li, Goran Zuzic
2018	J	`jnl`	Minor Excluded Network Families Admit Fast Distributed Algorithms. CoRR Bernhard Haeupler, Jason Li, Goran Zuzic
2018	J	`jnl`	Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing. CoRR Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
2018	J	`jnl`	Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions. CoRR Bernhard Haeupler
2018	A*	`conf`	Optimal Gossip Algorithms for Exact and Approximate Quantile Computations. PODC Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su
2018	J	`jnl`	Optimal strategies for patrolling fences. CoRR Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister
2018	A*	`conf`	Round- and Message-Optimal Distributed Graph Algorithms. PODC Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
2018	J	`jnl`	Round- and Message-Optimal Distributed Part-Wise Aggregation. CoRR Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc
2018	A*	`conf`	Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. ICALP Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik
2018	J	`jnl`	Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets. CoRR Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu
2018	A*	`conf`	Synchronization Strings: List Decoding for Insertions and Deletions. ICALP Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
2018	J	`jnl`	Synchronization Strings: List Decoding for Insertions and Deletions. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
2018	A*	`conf`	Synchronization strings: explicit constructions, local decoding, and applications. STOC Bernhard Haeupler, Amirbehshad Shahrasbi
2017	J	`jnl`	Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. Distributed Comput. Ofer Feinerman, Bernhard Haeupler, Amos Korman
2017	A*	`conf`	Bridging the Capacity Gap Between Interactive and One-Way Communication. SODA Bernhard Haeupler, Ameya Velingker
2017	A*	`conf`	Broadcasting in Noisy Radio Networks. PODC Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2017	J	`jnl`	Broadcasting in Noisy Radio Networks. CoRR Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
2017	J	`jnl`	Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. SIAM J. Comput. Ran Gelles, Bernhard Haeupler
2017	J	`jnl`	Making Asynchronous Distributed Computations Robust to Noise. CoRR Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler
2017	J	`jnl`	Optimal Gossip Algorithms for Exact and Approximate Quantile Computations. CoRR Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su
2017	J	`jnl`	Parallel Algorithms and Concentration Bounds for the Lovász Local Lemma via Witness DAGs. ACM Trans. Algorithms Bernhard Haeupler, David G. Harris
2017	A*	`conf`	Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs. SODA Bernhard Haeupler, David G. Harris
2017	J	`jnl`	Rumor Spreading with No Dependence on Conductance. SIAM J. Comput. Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
2017	J	`jnl`	Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik
2017	J	`jnl`	Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi
2017	J	`jnl`	Synchronization Strings: Explicit Constructions, Local Decoding, and Applications. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi
2017	A*	`conf`	Synchronization strings: codes for insertions and deletions approaching the Singleton bound. STOC Bernhard Haeupler, Amirbehshad Shahrasbi
2017	J	`jnl`	Tight Bounds on Vertex Connectivity Under Sampling. ACM Trans. Algorithms Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
2016	A*	`conf`	A Faster Distributed Radio Broadcast Primitive: Extended Abstract. PODC Bernhard Haeupler, David Wajc
2016	J	`jnl`	Analyzing Network Coding (Gossip) Made Easy. J. ACM Bernhard Haeupler
2016	J	`jnl`	Bridging the Capacity Gap Between Interactive and One-Way Communication. CoRR Bernhard Haeupler, Ameya Velingker
2016	J	`jnl`	Bridging the Capacity Gap Between Interactive and One-Way Communication. Electron. Colloquium Comput. Complex. Bernhard Haeupler, Ameya Velingker
2016	A*	`conf`	Constant-rate coding for multiparty interactive communication is impossible. STOC Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	Discovery Through Gossip. Random Struct. Algorithms Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
2016	A*	`conf`	Distributed Algorithms for Planar Networks I: Planar Embedding. PODC Mohsen Ghaffari, Bernhard Haeupler
2016	A*	`conf`	Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. SODA Mohsen Ghaffari, Bernhard Haeupler
2016	A*	`conf`	Low-Congestion Shortcuts without Embedding. PODC Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
2016	J	`jnl`	Low-Congestion Shortcuts without Embedding. CoRR Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
2016	J	`jnl`	Maximal Noise in Interactive Communication Over Erasure Channels and Channels With Feedback. IEEE Trans. Inf. Theory Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	Near-Optimal BFS-Tree Construction in Radio Networks. IEEE Commun. Lett. Mohsen Ghaffari, Bernhard Haeupler
2016	A	`conf`	Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs. DISC Bernhard Haeupler, Taisuke Izumi, Goran Zuzic
2016	A*	`conf`	Reliable Communication over Highly Connected Noisy Networks. PODC Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2016	J	`jnl`	SplayNet: Towards Locally Self-Adjusting Networks. IEEE/ACM Trans. Netw. Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker
2016	A*	`conf`	Towards Optimal Deterministic Coding for Interactive Communication. SODA Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2015	J	`jnl`	Bounded-Contention Coding for the additive network model. Distributed Comput. Keren Censor-Hillel, Bernhard Haeupler, Nancy A. Lynch, Muriel Médard
2015	A*	`conf`	Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. SODA Ran Gelles, Bernhard Haeupler
2015	—	`conf`	Communication with Partial Noiseless Feedback. APPROX-RANDOM Bernhard Haeupler, Pritish Kamath, Ameya Velingker
2015	J	`jnl`	Constant-rate coding for multiparty interactive communication is impossible. Electron. Colloquium Comput. Complex. Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	A*	`conf`	Distributed Resource Discovery in Sub-Logarithmic Time. PODC Bernhard Haeupler, Dahlia Malkhi
2015	J	`jnl`	Improved bounds and parallel algorithms for the Lovasz Local Lemma. CoRR Bernhard Haeupler, David G. Harris
2015	A	`conf`	Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. ITCS Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. CoRR Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	Network Coding Based Information Spreading in Dynamic Networks With Correlated Data. IEEE J. Sel. Areas Commun. Asaf Cohen, Bernhard Haeupler, Chen Avin, Muriel Médard
2015	J	`jnl`	Randomized broadcast in radio networks with collision detection. Distributed Comput. Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2015	J	`jnl`	Rank-Balanced Trees. ACM Trans. Algorithms Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2015	J	`jnl`	Reliable Communication over Highly Connected Noisy Networks. Electron. Colloquium Comput. Complex. Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
2015	J	`jnl`	Self-adjusting grid networks to minimize expected path length. Theor. Comput. Sci. Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker
2015	J	`jnl`	Simple, Fast and Deterministic Gossip and Rumor Spreading. J. ACM Bernhard Haeupler
2015	A*	`conf`	Tight Bounds on Vertex Connectivity Under Vertex Sampling. SODA Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn
2015	J	`jnl`	Towards Optimal Deterministic Coding for Interactive Communication. Electron. Colloquium Comput. Complex. Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson
2014	A*	`conf`	Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. PODC Ofer Feinerman, Bernhard Haeupler, Amos Korman
2014	A*	`conf`	Broadcast Throughput in Radio Networks: Routing vs. Network Coding. SODA Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2014	J	`jnl`	Consistent Weighted Sampling Made Fast, Small, and Easy. CoRR Bernhard Haeupler, Mark S. Manasse, Kunal Talwar
2014	J	`jnl`	Fast Structuring of Radio Networks for Multi-Message Communications. CoRR Mohsen Ghaffari, Bernhard Haeupler
2014	A*	`conf`	Interactive Channel Capacity Revisited. FOCS Bernhard Haeupler
2014	J	`jnl`	Interactive Channel Capacity Revisited. CoRR Bernhard Haeupler
2014	A*	`conf`	Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. FOCS Mohsen Ghaffari, Bernhard Haeupler
2014	J	`jnl`	Optimal Gossip with Direct Addressing. CoRR Bernhard Haeupler, Dahlia Malkhi
2014	A*	`conf`	Optimal error rates for interactive coding I: adaptivity and other settings. STOC Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
2014	A*	`conf`	Optimal gossip with direct addressing. PODC Bernhard Haeupler, Dahlia Malkhi
2014	J	`jnl`	Randomized Broadcast in Radio Networks with Collision Detection. CoRR Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2014	B	`conf`	Repeated deletion channels. ITW Bernhard Haeupler, Michael Mitzenmacher
2013	J	`jnl`	A Bound on the Throughput of Radio Networks CoRR Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2013	J	`jnl`	Beeping a maximal independent set. Distributed Comput. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
2013	J	`jnl`	Deterministic Algorithms for the Lovász Local Lemma. SIAM J. Comput. Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
2013	J	`jnl`	Efficient and Noise-Resilient rumor-spreading in Large, Anonymous Populations. CoRR Ofer Feinerman, Bernhard Haeupler, Amos Korman
2013	A	`conf`	Fast Structuring of Radio Networks Large for Multi-message Communications. DISC Mohsen Ghaffari, Bernhard Haeupler
2013	A	`conf`	Locally Self-Adjusting Tree Networks. IPDPS Chen Avin, Bernhard Haeupler, Zvi Lotker, Christian Scheideler, Stefan Schmid
2013	A*	`conf`	Near Optimal Leader Election in Multi-Hop Radio Networks. SODA Mohsen Ghaffari, Bernhard Haeupler
2013	J	`jnl`	Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. CoRR Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
2013	J	`jnl`	Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. CoRR Mohsen Ghaffari, Bernhard Haeupler
2013	—	`—`	Probabilistic methods for distributed information dissemination. Bernhard Haeupler
2013	A*	`conf`	Randomized broadcast in radio networks with collision detection. PODC Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2013	B	`conf`	Self-adjusting Grid Networks to Minimize Expected Path Length. SIROCCO Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker
2013	A*	`conf`	Simple, Fast and Deterministic Gossip and Rumor Spreading. SODA Bernhard Haeupler
2013	J	`jnl`	Testing Simultaneous Planarity when the Common Graph is 2-Connected. J. Graph Algorithms Appl. Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw
2012	J	`jnl`	Beeping a Maximal Independent Set CoRR Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
2012	J	`jnl`	Bounded-Contention Coding for Wireless Networks in the High SNR Regime CoRR Keren Censor-Hillel, Bernhard Haeupler, Nancy A. Lynch, Muriel Médard
2012	A	`conf`	Bounded-Contention Coding for Wireless Networks in the High SNR Regime. DISC Keren Censor-Hillel, Bernhard Haeupler, Nancy A. Lynch, Muriel Médard
2012	J	`jnl`	Bounds on Contention Management in Radio Networks CoRR Mohsen Ghaffari, Bernhard Haeupler, Nancy A. Lynch, Calvin C. Newport
2012	A	`conf`	Bounds on Contention Management in Radio Networks. DISC Mohsen Ghaffari, Bernhard Haeupler, Nancy A. Lynch, Calvin C. Newport
2012	A	`conf`	Brief Announcement: SplayNets - Towards Self-Adjusting Distributed Data Structures. DISC Stefan Schmid, Chen Avin, Christian Scheideler, Bernhard Haeupler, Zvi Lotker
2012	J	`jnl`	Discovery through Gossip CoRR Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
2012	B	`conf`	Discovery through gossip. SPAA Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
2012	A*	`conf`	Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. STOC Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
2012	J	`jnl`	Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance. ACM Trans. Algorithms Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan
2012	J	`jnl`	Lower Bounds on Information Dissemination in Dynamic Networks CoRR Bernhard Haeupler, Fabian Kuhn
2012	A	`conf`	Lower Bounds on Information Dissemination in Dynamic Networks. DISC Bernhard Haeupler, Fabian Kuhn
2012	J	`jnl`	Near Optimal Leader Election in Multi-Hop Radio Networks CoRR Mohsen Ghaffari, Bernhard Haeupler
2012	J	`jnl`	Network Coded Gossip with Correlated Data CoRR Bernhard Haeupler, Asaf Cohen, Chen Avin, Muriel Médard
2012	B	`conf`	Network coded gossip with correlated data. ISIT Bernhard Haeupler, Asaf Cohen, Chen Avin, Muriel Médard
2012	J	`jnl`	Simple, Fast and Deterministic Gossip and Rumor Spreading CoRR Bernhard Haeupler
2012	J	`jnl`	The Complexity of Multi-Message Broadcast in Radio Networks with Known Topology CoRR Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
2012	J	`jnl`	Tighter Worst-Case Bounds on Algebraic Gossip CoRR Bernhard Haeupler
2012	J	`jnl`	Tighter Worst-Case Bounds on Algebraic Gossip. IEEE Commun. Lett. Bernhard Haeupler
2011	A*	`conf`	Analyzing network coding gossip made easy. STOC Bernhard Haeupler
2011	A	`conf`	Beeping a Maximal Independent Set. DISC Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
2011	J	`jnl`	Computing a Maximal Independent Set Using Beeps CoRR Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
2011	J	`jnl`	Faster Information Dissemination in Dynamic Networks via Network Coding CoRR Bernhard Haeupler, David R. Karger
2011	A*	`conf`	Faster information dissemination in dynamic networks via network coding. PODC Bernhard Haeupler, David R. Karger
2011	J	`jnl`	Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance CoRR Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov
2011	J	`jnl`	Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance CoRR Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan
2011	J	`jnl`	Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive. Electron. J. Comb. William I. Gasarch, Bernhard Haeupler
2011	J	`jnl`	New Constructive Aspects of the Lovász Local Lemma. J. ACM Bernhard Haeupler, Barna Saha, Aravind Srinivasan
2011	J	`jnl`	One Packet Suffices - Highly Efficient Packetized Network Coding With Finite Memory CoRR Bernhard Haeupler, Muriel Médard
2011	B	`conf`	One packet suffices - Highly efficient packetized Network Coding With finite memory. ISIT Bernhard Haeupler, Muriel Médard
2011	—	`conf`	Online Stochastic Weighted Matching: Improved Approximation Algorithms. WINE Bernhard Haeupler, Vahab S. Mirrokni, Morteza Zadimoghaddam
2011	J	`jnl`	Optimality of Network Coding in Packet Networks CoRR Bernhard Haeupler, Minji Kim, Muriel Médard
2011	B	`conf`	Optimality of network coding with buffers. ITW Bernhard Haeupler, Minji Kim, Muriel Médard
2011	J	`jnl`	Rank-Pairing Heaps. SIAM J. Comput. Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2011	J	`jnl`	Self-Adjusting Networks to Minimize Expected Path Length CoRR Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Lotker
2010	J	`jnl`	Analyzing Network Coding Gossip Made Easy CoRR Bernhard Haeupler
2010	A*	`conf`	Deterministic Algorithms for the Lovász Local Lemma. SODA Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
2010	J	`jnl`	New Constructive Aspects of the Lovasz Local Lemma CoRR Bernhard Haeupler, Barna Saha, Aravind Srinivasan
2010	A*	`conf`	New Constructive Aspects of the Lovasz Local Lemma. FOCS Bernhard Haeupler, Barna Saha, Aravind Srinivasan
2010	J	`jnl`	Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections CoRR Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
2010	—	`conf`	Testing Simultaneous Planarity When the Common Graph Is 2-Connected. ISAAC (2) Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw
2010	J	`jnl`	Testing Simultaneous Planarity when the Common Graph is 2-Connected CoRR Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw
2009	J	`jnl`	Deterministic Algorithms for the Lovasz Local Lemma CoRR Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler
2009	J	`jnl`	Heaps Simplified CoRR Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2009	B	`conf`	Rank-Balanced Trees. WADS Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2009	A	`conf`	Rank-Pairing Heaps. ESA Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2009	J	`jnl`	Robust Regulatory Networks CoRR Arnab Bhattacharyya, Bernhard Haeupler
2008	—	`conf`	Faster Algorithms for Incremental Topological Ordering. ICALP (1) Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan
2008	J	`jnl`	Finding a feasible flow in a strongly connected network. Oper. Res. Lett. Bernhard Haeupler, Robert Endre Tarjan
2008	J	`jnl`	Incremental Topological Ordering and Strong Component Maintenance CoRR Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan
2008	J	`jnl`	Planarity Algorithms via PQ-Trees (Extended Abstract). Electron. Notes Discret. Math. Bernhard Haeupler, Robert Endre Tarjan
2007	J	`jnl`	Finding a Feasible Flow in a Strongly Connected Network CoRR Bernhard Haeupler, Robert Endre Tarjan