Bernhard Haeupler
Post-Prof. & Researcher, ETH Zurich, Computer Science Department (2020 - now)
Professor, Carnegie Mellon University, Computer Science Department (2014 - now)
(2014 - 2019 Assistant Prof.; 2019 - 2022 Associate Prof.; since 2022 Adjunct Prof.)
Advocate for Neurodiversity and Diversity

139. Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
     with Vaclav Rozhon, Anders Martinsson, Christoph Grunau, Goran Zuzic
     STOC: ACM Symposium on Theory of Computing, 2023
     (ArXiv)        
     
     
140. Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
     with D. Ellis Hershkowitz; Thatchaphol Saranurak
     STOC: ACM Symposium on Theory of Computing, 2023
     (ArXiv)        
     
     
141. Sparse Semi-Oblivious Routing: Few Random Paths Suffice
     with Goran Zuzic, Antti Roeyskoe
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2023
     (ArXiv)        
     
     
142. Improved Distributed Network Decomposition, Hitting Sets, and Spanners via Derandomization
     with Mohsen Ghaffari, Christoph Grunau, Saeed Ilchi, Vaclav Rozhon
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2023
     (ArXiv)        (Download)        
     
     
143. Interactive Coding with Small Memory
     with Klim Efremenko, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2023
     (Download)        
     
     
144. A Simple Deterministic Distributed Low-Diameter Clustering
     with Vaclav Rozhon, Christoph Grunau
     SOSA: SIAM Symposium on Simplicity in Algorithms, 2023
     (ArXiv)        (Download)        
     
     
145. Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
     with Vaclav Rozhon, Michael Elkin, Christoph Grunau
     FOCS: IEEE Symposium on Foundations of Computer Science, 2022
     (ArXiv)        (Download)        
     
     
146. Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality
     with Harald Räcke, Mohsen Ghaffari
     STOC: ACM Symposium on Theory of Computing, 2022
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC22p1338,
       title={Hop-Constrained Expander Decompositions, Oblivious Routing, and Distributed Universal Optimality },
       author={Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2022},
       pages={1325--1338},
       doi={10.1145/3519935.3520026}}
            
     
     
147. Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms
     with Vaclav Rozhon, Christoph Grunau, Goran Zuzic, Jason Li
     STOC: ACM Symposium on Theory of Computing, 2022
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC22p,
       title={Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms},
       author={Vaclav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2022},
       pages={478--},
       doi={10.1145/3519935.3520074}}
            
     
     
148. Circuits Resilient to Short-Circuit Errors
     with Klim Efremenko, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
     STOC: ACM Symposium on Theory of Computing, 2022
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC22p594,
       title={Circuits Resilient to Short-Circuit Errors},
       author={Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena },
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2022},
       pages={582--594},
       doi={10.1145/3519935.3520007}}
            
     
     
149. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
     with Goran Zuzic, Gramoz Goranci, Mingquan Ye, Xiaorui Sun
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2022
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA22p2579,
       title={Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing},
       author={Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2022},
       pages={2549--2579},
       doi={10.1137/1.9781611977073.100}}
            
     
     
150. Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
     with Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Saeed Ilchi, Vaclav Rozhon
     SPAA: ACM Symposium on Parallelism in Algorithms and Architectures, 2022
     (ArXiv)        (Download)        
     
     
151. Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
     with Ioannis Anagnostides, Christoph Lenzen, Goran Zuzic, Themis Gouleakis
     DISC: International Symposium on Distributed Computing, 2022
     (ArXiv)        (Download)        
     
     
152. Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes
     with Amirbehshad Shahrasbi
     ITW: IEEE Information Theory Workshop, 2022
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITW22p475,
       title={Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes},
       author={Bernhard Haeupler, Amirbehshad Shahrasbi},
       journal={Proceeding of the IEEE Information Theory Workshop (ITW)},
       year={2022},
       pages={470--475},
       doi={10.1109/ITW54588.2022.9965935}}
            
     
     
153. Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings
     with D. Ellis Hershkowitz and Goran Zuzic
     ESA: European Symposium on Algorithms, 2022
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerESA22p63:14,
       title={Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings},
       author={Bernhard Haeupler, D. Ellis Hershkowitz and Goran Zuzic},
       journal={Proceeding of the European Symposium on Algorithms (ESA)},
       year={2022},
       pages={63:1--63:14},
       doi={10.4230/LIPIcs.ESA.2022.63}}
            
     
     
154. Hop-Constrained Oblivious Routing
     with Mohsen Ghaffari, Goran Zuzic
     STOC: ACM Symposium on Theory of Computing, 2021
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC21p1220,
       title={Hop-Constrained Oblivious Routing},
       author={Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2021},
       pages={1208--1220},
       doi={10.1145/3406325.3451098}}
            
     
     
155. Universally-Optimal Distributed Algorithms for Known Topologies
     with David Wajc, Goran Zuzic
     STOC: ACM Symposium on Theory of Computing, 2021
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC21p1179,
       title={Universally-Optimal Distributed Algorithms for Known Topologies},
       author={Bernhard Haeupler, David Wajc, Goran Zuzic},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2021},
       pages={1166--1179},
       doi={10.1145/3406325.3451081}}
            
     
     
156. Tree Embeddings for Hop-Constrained Network Design
     with Ellis Hershkowitz, Goran Zuzic
     STOC: ACM Symposium on Theory of Computing, 2021
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC21p379,
       title={Tree Embeddings for Hop-Constrained Network Design},
       author={Bernhard Haeupler, Ellis Hershkowitz, Goran Zuzic },
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2021},
       pages={356--379},
       doi={10.1145/3406325.3451053}}
            
     
     
157. Low-Congestion Shortcuts for Graphs Excluding Dense Minors
     with Mohsen Ghaffari
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2021
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC21p221,
       title={Low-Congestion Shortcuts for Graphs Excluding Dense Minors},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2021},
       pages={213--221},
       doi={10.1145/3465084.3467935}}
            
     
     
158. Efficient Linear and Affine Codes for Correcting Insertions/Deletions
     with Kuan Cheng, Venkatesan Guruswami, Xin Li
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2021
     (ArXiv)        (Download)        
     
     
159. A Time-Optimal Randomized Parallel Algorithm for MIS
     with Mohsen Ghaffari
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2021
     (Download)        
     
     
160. Near-Optimal Schedules for Simultaneous Multicasts
     with David Ellis Hershkowitz, David Wajc
     ICALP: International Colloquium on Automata, Languages and Programming, 2021
     (ArXiv)        (Download)        
     
     
161. Network Coding Gaps for Completion Times of Multiple Unicasts
     with David Wajc, Goran Zuzic
     FOCS: IEEE Symposium on Foundations of Computer Science, 2020
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerFOCS20p505,
       title={Network Coding Gaps for Completion Times of Multiple Unicasts},
       author={Bernhard Haeupler, David Wajc, Goran Zuzic},
       journal={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
       year={2020},
       pages={494--505},
       doi={10.1109/FOCS46700.2020.00053}}
            
     
     
162. Optimally Resilient Codes for List-Decoding from Insertions and Deletions
     with Amirbehshad Shahrasbi, Venkatesan Guruswami
     STOC: ACM Symposium on Theory of Computing, 2020
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC20p537,
       title={Optimally Resilient Codes for List-Decoding from Insertions and Deletions},
       author={Bernhard Haeupler, Amirbehshad Shahrasbi, Venkatesan Guruswami},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2020},
       pages={524--537},
       doi={10.1145/3357713.3384262}}
            
     
     
163. Writeback Aware Caching
     with Nathan Beckmann, Phillip Gibbons, Charles McGuffey
     APOCS: ACM-SIAM Symposium on Algorithmic Principles of Computer Systems, 2020
     Best Paper Award
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerAPOCS20p15,
       title={Writeback Aware Caching},
       author={Nathan Beckmann, Phillip Gibbons, Bernhard Haeupler, Charles McGuffey},
       journal={Proceeding of the ACM-SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS)},
       year={2020},
       pages={1--15},
       doi={10.1137/1.9781611976021.1}}
            
     
     
164. Computation-Aware Data Aggregation
     with Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia
     ITCS: ACM-SIGACT Innovations in Theoretical Computer Science Conference, 2020
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITCS20p65:38,
       title={Computation-Aware Data Aggregation},
       author={Bernhard Haeupler, Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia},
       journal={Proceeding of the ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS)},
       year={2020},
       pages={65:1--65:38},
       doi={10.4230/LIPIcs.ITCS.2020.65}}
            
     
     
165. Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions
     Bernhard Haeupler
     FOCS: IEEE Symposium on Foundations of Computer Science, 2019
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerFOCS19p347,
       title={Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions},
       author={Bernhard Haeupler},
       journal={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
       year={2019},
       pages={ 334--347},
       doi={10.1109/FOCS.2019.00029}}
            
     
     
166. Near-Linear Time Insertion-Deletion Codes and (1+eps)-Approximating Edit Distance via Indexing
     with Aviad Rubinstein, Amirbehshad Shahrasbi
     STOC: ACM Symposium on Theory of Computing, 2019
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC19p708,
       title={Near-Linear Time Insertion-Deletion Codes and (1+eps)-Approximating Edit Distance via Indexing},
       author={Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2019},
       pages={697--708},
       doi={10.1145/3313276.3316371}}
            
     
     
167. Erasure Correction for Noisy Radio Networks
     with Keren Censor-Hillel, Ellis Hershkowitz, Goran Zuzic
     DISC: International Symposium on Distributed Computing, 2019
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC19p10:17,
       title={Erasure Correction for Noisy Radio Networks},
       author={Keren Censor-Hillel, Bernhard Haeupler, Ellis Hershkowitz, Goran Zuzic},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2019},
       pages={10:1--10:17},
       doi={10.4230/LIPIcs.DISC.2019.10}}
            
     
     
168. Optimal strategies for patrolling fences
     with Fabian Kuhn, Anders Martinsson, Kalina Petrova, Pascal Pfister
     ICALP: International Colloquium on Automata, Languages and Programming, 2019
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{Haeuplersub18p,
       title={Synchronization Strings over Small Alphabets},
       author={Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu},
       inproceedings={in submission (sub)},
       year={2018},
       pages={--},
       doi={}}
            
     
     
169. Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets
     with Kuan Cheng, Xin Li, Amirbehshad Shahrasbi, Ke Wu
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2019
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{Haeuplersub18p,
       title={Synchronization Strings over Small Alphabets},
       author={Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu},
       inproceedings={in submission (sub)},
       year={2018},
       pages={--},
       doi={}}
            
     
     
170. Synchronization Strings: Explicit Constructions, Local Decoding, and Applications
     with Amirbehshad Shahrasbi
     STOC: ACM Symposium on Theory of Computing, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC18p46,
       title={Synchronization Strings: Explicit Constructions, Local Decoding, and Applications },
       author={Bernhard Haeupler, Amirbehshad Shahrasbi},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2018},
       pages={33--46},
       doi={10.1145/3188745.3188940}}
            
     
     
171. Explicit Binary Tree Codes with Polylogarithmic Size Alphabet
     with Gil Cohen, Leonard Schulman
     STOC: ACM Symposium on Theory of Computing, 2018
     Invited to the SIAM Journal of Computing Special Issue for STOC 2018
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC18p544,
       title={Explicit Binary Tree Codes with Polylogarithmic Size Alphabet},
       author={Gil Cohen, Bernhard Haeupler, Leonard Schulman},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2018},
       pages={535--544},
       doi={10.1145/3188745.3188928}}
            
     
     
172. Minor Excluded Network Families Admit Fast Distributed Algorithms
     with Jason Li, Goran Zuzic
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC18p474,
       title={Minor Excluded Network Families Admit Fast Distributed Algorithms},
       author={Bernhard Haeupler, Jason Li, Goran Zuzic},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2018},
       pages={465--474},
       doi={10.1145/3212734.3212776}}
            
     
     
173. Round- and Message- Optimal Distributed Graph Algorithms
     with Ellis Hershkowitz, David Wacj
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC18p128,
       title={Round- and Message- Optimal Distributed Graph Algorithms},
       author={Bernhard Haeupler, Ellis Hershkowitz, David Wacj},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2018},
       pages={119--128},
       doi={10.1145/3212734.3212737}}
            
     
     
174. Optimal Gossip Algorithms for Exact and Approximate Quantile Computations
     with Jeet Mohapatra, Hsin-Hao Su
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC18p188,
       title={Optimal Gossip Algorithms for Exact and Approximate Quantile Computations},
       author={Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2018},
       pages={179--188},
       doi={10.1145/3212734.3212770}}
            
     
     
175. Synchronization Strings: List Decoding for Insertions and Deletions
     with Amirbehshad Shahrasbi, Madhu Sudan
     ICALP: International Colloquium on Automata, Languages and Programming, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerICALP18p76:14,
       title={Synchronization Strings: List Decoding for Insertions and Deletions},
       author={Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan},
       journal={Proceeding of the International Colloquium on Automata, Languages and Programming (ICALP)},
       year={2018},
       pages={76:1--76:14},
       doi={10.4230/LIPIcs.ICALP.2018.76}}
            
     
     
176. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions
     with Amirbehshad Shahrasbi, Ellen Vitercik
     ICALP: International Colloquium on Automata, Languages and Programming, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerICALP18p75:14,
       title={Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions},
       author={Bernhard Haeupler, Amirbehshad Shahrasbi, Ellen Vitercik},
       journal={Proceeding of the International Colloquium on Automata, Languages and Programming (ICALP)},
       year={2018},
       pages={75:1--75:14},
       doi={10.4230/LIPIcs.ICALP.2018.75}}
            
     
     
177. Algorithms for Noisy Broadcast with Erasures
     with Ofer Grossman, Sidhanth Mohanty
     ICALP: International Colloquium on Automata, Languages and Programming, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerICALP18p153:12,
       title={Algorithms for Noisy Broadcast with Erasures},
       author={Ofer Grossman, Bernhard Haeupler and Sidhanth Mohanty},
       journal={Proceeding of the International Colloquium on Automata, Languages and Programming (ICALP)},
       year={2018},
       pages={153:1--153:12},
       doi={10.4230/LIPIcs.ICALP.2018.153}}
            
     
     
178. Faster Distributed Shortest Path Approximations via Shortcuts
     with Jason Li
     DISC: International Symposium on Distributed Computing, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC18p33:14,
       title={Faster Distributed Shortest Path Approximations via Shortcuts},
       author={Bernhard Haeupler, Jason Li},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2018},
       pages={33:1--33:14},
       doi={10.4230/LIPIcs.DISC.2018.33}}
            
     
     
179. Allocate-On-Use Space Complexity of Shared-Memory Algorithms
     with James Aspnes, Alexander Tong, Philipp Woelfl
     DISC: International Symposium on Distributed Computing, 2018
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC18p8:17,
       title={Allocate-On-Use Space Complexity of Shared-Memory Algorithms},
       author={James Aspnes, Bernhard Haeupler, Alexander Tong, Philipp Woelfl},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2018},
       pages={8:1--8:17},
       doi={10.4230/LIPIcs.DISC.2018.8}}
            
     
     
180. Making Asynchronous Distributed Computations Robust to Noise
     with Keren Censor-Hillel, Ran Gelles
     ITCS: ACM-SIGACT Innovations in Theoretical Computer Science Conference, 2018
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITCS18p50:20,
       title={Making Asynchronous Distributed Computations Robust to Noise},
       author={Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS)},
       year={2018},
       pages={50:1--50:20},
       doi={10.4230/LIPIcs.ITCS.2018.50}}
            
     
     
181. Broadcasting in Noisy Radio Networks
     with Keren Censor-Hillel, Ellis Hershkowitz, Goran Zuzic
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2017
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC17p42,
       title={Broadcasting in Noisy Radio Networks},
       author={Keren Censor-Hillel, Bernhard Haeupler, Ellis Hershkowitz, Goran Zuzic},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2017},
       pages={33--42},
       doi={10.1145/3087801.3087808}}
            
     
     
182. Bridging the Capacity Gap Between Interactive and One-Way Communication
     with Ameya Velingker
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2017
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA17p2142,
       title={Bridging the Capacity Gap Between Interactive and One-Way Communication},
       author={Bernhard Haeupler, Ameya Velingker},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2017},
       pages={2123--2142},
       doi={10.1137/1.9781611974782.138}}
            
     
     
183. Parallel algorithms and Concentration bounds and for the Lovasz Local Lemma via Witness-DAGs
     with David Harris
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2017
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA17p1187,
       title={Parallel algorithms and Concentration bounds and for the Lovasz Local Lemma via Witness-DAGs},
       author={Bernhard Haeupler, David Harris},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2017},
       pages={1170--1187},
       doi={10.1137/1.9781611974782.76}}
            
     
     
184. Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
     with Amirbehshad Shahrasbi
     STOC: ACM Symposium on Theory of Computing, 2017
     Invited to the Theory of Computing Journal
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC17p46,
       title={Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound},
       author={Bernhard Haeupler, Amirbehshad Shahrasbi},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2017},
       pages={33--46},
       doi={10.1145/3055399.3055498}}
            
     
     
185. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
     with Taisuke Izumi, Goran Zuzic
     DISC: International Symposium on Distributed Computing, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC16p172,
       title={Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs},
       author={Bernhard Haeupler, Taisuke Izumi, Goran Zuzic},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2016},
       pages={158--172},
       doi={10.1007/978-3-662-53426-7_12}}
            
     
     
186. A Faster Distributed Radio Broadcast Primitive
     with David Wajc
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC16p370,
       title={A Faster Distributed Radio Broadcast Primitive},
       author={Bernhard Haeupler, David Wajc},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2016},
       pages={361--370},
       doi={10.1145/2933057.2933121}}
            
     
     
187. Low-Congestion Shortcuts without Embedding
     with Taisuke Izumi, Goran Zuzic
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2016
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC16p460,
       title={Low-Congestion Shortcuts without Embedding},
       author={Bernhard Haeupler, Taisuke Izumi, Goran Zuzic},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2016},
       pages={451--460},
       doi={10.1145/2933057.2933112}}
            
     
     
188. Distributed Algorithms for Planar Graphs: Planar Embeddings
     with Mohsen Ghaffari
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC16p38,
       title={Distributed Algorithms for Planar Graphs: Planar Embeddings},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2016},
       pages={29--38},
       doi={10.1145/2933057.2933109}}
            
     
     
189. Reliable Communication over Highly Connected Noisy Networks
     with Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2016
     Invited to the Distributed Computing Special Issue for PODC 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC16p173,
       title={Reliable Communication over Highly Connected Noisy Networks},
       author={Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2016},
       pages={165--173},
       doi={10.1145/2933057.2933085}}
            
     
     
190. Constant-rate coding for multiparty interactive communication is impossible
     with Mark Braverman, Klim Efremenko, Ran Gelles
     STOC: ACM Symposium on Theory of Computing, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC16p1010,
       title={Constant-rate coding for multiparty interactive communication is impossible},
       author={Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2016},
       pages={999--1010},
       doi={10.1145/2897518.2897563}}
            
     
     
191. Distributed Algorithms for Planar Graphs: Low Congestion Shortcuts, MST, and Min-Cut
     with Mohsen Ghaffari
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA16p219,
       title={Distributed Algorithms for Planar Graphs: Low Congestion Shortcuts, MST, and Min-Cut},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2016},
       pages={202--219},
       doi={10.1137/1.9781611974331.ch16}}
            
     
     
192. Towards optimal deterministic coding for interactive communication
     with Ran Gelles, Gillat Kol, Noga Ron-Zewi and Avi Wigderson
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2016
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA16p1936,
       title={Towards optimal deterministic coding for interactive communication},
       author={Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi and Avi Wigderson},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2016},
       pages={1922--1936},
       doi={10.1137/1.9781611974331.ch135}}
            
     
     
193. Communication with Partial Noiseless Feedback
     with Pritish Kamath, Ameya Velingker
     RANDOM: International Workshop on Randomization and Computation, 2015
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerRANDOM15p897,
       title={Communication with Partial Noiseless Feedback},
       author={Bernhard Haeupler, Pritish Kamath, Ameya Velingker},
       journal={Proceeding of the International Workshop on Randomization and Computation (RANDOM)},
       year={2015},
       pages={881--897},
       doi={10.4230/LIPIcs.APPROX-RANDOM.2015.881}}
            
     
     
194. Distributed Resource Discovery in Sub-Logarithmic Time
     with Dahlia Malkhi
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2015
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC15p419,
       title={Distributed Resource Discovery in Sub-Logarithmic Time},
       author={Bernhard Haeupler, Dahlia Malkhi},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2015},
       pages={413--419},
       doi={10.1145/2767386.2767435}}
            
     
     
195. Tight Bounds on Vertex Connectivity under Vertex Sampling
     with Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Fabian Kuhn
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2015
     Invited to the Transactions of Algorithms Special Issue for SODA 2015
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA15p2018,
       title={Tight Bounds on Vertex Connectivity under Vertex Sampling},
       author={Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2015},
       pages={2006--2018},
       doi={10.1137/1.9781611973730.133}}
            
     
     
196. Capacity of Interactive Communication over Erasure Channels and Channels with Feedback
     with Ran Gelles
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2015
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA15p1311,
       title={Capacity of Interactive Communication over Erasure Channels and Channels with Feedback},
       author={Ran Gelles, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2015},
       pages={1296--1311},
       doi={10.1137/1.9781611973730.86}}
            
     
     
197. Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback
     with Klim Efremenko, Ran Gelles
     ITCS: ACM-SIGACT Innovations in Theoretical Computer Science Conference, 2015
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITCS15p20,
       title={Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback},
       author={Klim Efremenko, Ran Gelles, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS)},
       year={2015},
       pages={11--20},
       doi={10.1145/2688073.2688077}}
            
     
     
198. Interactive Channel Capacity Revisited
     Bernhard Haeupler
     FOCS: IEEE Symposium on Foundations of Computer Science, 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerFOCS14p235,
       title={Interactive Channel Capacity Revisited},
       author={Bernhard Haeupler},
       journal={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
       year={2014},
       pages={226--235},
       doi={10.1109/FOCS.2014.32}}
            
     
     
199. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
     with Mohsen Ghaffari
     FOCS: IEEE Symposium on Foundations of Computer Science, 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerFOCS14p403,
       title={Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
       year={2014},
       pages={394--403},
       doi={10.1109/FOCS.2014.49}}
            
     
     
200. Repeated Deletion Channels
     with Michael Mitzenmacher
     ITW: IEEE Information Theory Workshop, 2014
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITW14p156,
       title={Repeated Deletion Channels},
       author={Bernhard Haeupler, Michael Mitzenmacher},
       journal={Proceeding of the IEEE Information Theory Workshop (ITW)},
       year={2014},
       pages={152--156},
       doi={10.1109/ITW.2014.6970811}}
            
     
     
201. Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited, and Anonymous Communication
     with Ofer Feinerman, Amos Korman
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2014
     Invited to the Distributed Computing Special Issue for PODC 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC14p123,
       title={Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited, and Anonymous Communication},
       author={Ofer Feinerman, Bernhard Haeupler, Amos Korman},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2014},
       pages={114--123},
       doi={10.1145/2611462.2611469}}
            
     
     
202. Optimal Gossip With Direct Addressing
     with Dahlia Malkhi
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2014
     Invited to the Distributed Computing Special Issue for PODC 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC14p185,
       title={Optimal Gossip With Direct Addressing},
       author={Bernhard Haeupler, Dahlia Malkhi},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2014},
       pages={176--185},
       doi={10.1145/2611462.2611489}}
            
     
     
203. Optimal Error Rates for Interactive Coding I: Adaptivity and other Settings
     with Mohsen Ghaffari, Madhu Sudan
     STOC: ACM Symposium on Theory of Computing, 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC14p803,
       title={Optimal Error Rates for Interactive Coding I: Adaptivity and other Settings},
       author={Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2014},
       pages={794--803},
       doi={10.1145/2591796.2591872}}
            
     
     
204. Broadcast Throughput in Radio Networks: Routing vs. Network Coding
     with Noga Alon, Mohsen Ghaffari, Majid Khabbazian
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2014
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA14p1843,
       title={Broadcast Throughput in Radio Networks: Routing vs. Network Coding},
       author={Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2014},
       pages={1831--1843},
       doi={10.1137/1.9781611973402.132}}
            
     
     
205. Fast Structuring of Radio Networks for Multi-Message Communications
     with Mohsen Ghaffari
     DISC: International Symposium on Distributed Computing, 2013
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC13p506,
       title={Fast Structuring of Radio Networks for Multi-Message Communications},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2013},
       pages={492--506},
       doi={10.1007/978-3-642-41527-2_34}}
            
     
     
206. Randomized Broadcast in Radio Networks with Collision Detection
     with Mohsen Ghaffari, Majid Khabbazian
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2013
     Invited to the Distributed Computing Special Issue for PODC 2013
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC13p334,
       title={Randomized Broadcast in Radio Networks with Collision Detection},
       author={Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2013},
       pages={325--334},
       doi={10.1145/2484239.2484248}}
            
     
     
207. Simple, Fast, and Deterministic Gossip and Rumor Spreading
     Bernhard Haeupler
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2013
     Winner of the SODA 2013 Best Student Paper Award
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA13p716,
       title={Simple, Fast, and Deterministic Gossip and Rumor Spreading},
       author={Bernhard Haeupler},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2013},
       pages={705--716},
       doi={}}
            
     
     
208. Near Optimal Leader Election in Multi-Hop Radio Networks
     with Mohsen Ghaffari
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2013
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA13p766,
       title={Near Optimal Leader Election in Multi-Hop Radio Networks},
       author={Mohsen Ghaffari, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2013},
       pages={748--766},
       doi={}}
            
     
     
209. Locally Self-Adjusting Tree Networks
     with Chen Avin, Michael Borokhovich, Zvi Loetker, Christian Scheideler, Stefan Schmid
     IPDPS: IEEE International Parallel and Distributed Processing Symposium, 2013
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerIPDPS13p406,
       title={Locally Self-Adjusting Tree Networks},
       author={Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Loetker, Christian Scheideler, Stefan Schmid},
       journal={Proceeding of the IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
       year={2013},
       pages={395--406},
       doi={10.1109/IPDPS.2013.40}}
            
     
     
210. Self-Adjusting Grid Networks to Minimize Expected Path Length
     with Chen Avin, Michael Borokhovich, Zvi Loetker
     SIROCCO: International Colloquium on Structural Information and Communication Complexity, 2013
     Invited to the Theoretical Computer Science Special Issue for SIROCCO 2013
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSIROCCO13p12,
       title={Self-Adjusting Grid Networks to Minimize Expected Path Length},
       author={Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Loetker},
       journal={Proceeding of the International Colloquium on Structural Information and Communication Complexity (SIROCCO)},
       year={2013},
       pages={1--12},
       doi={10.1007/978-3-319-03578-9_4}}
            
     
     
211. Global Computation in a Poorly Connected World: Fast Rumor Spreading No Dependence on Conductance
     with Keren Censor-Hillel, Jonathan Kelner, Petar Maymounkov
     STOC: ACM Symposium on Theory of Computing, 2012
     (ArXiv)        (Download)        (ACM Authorizer Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC12p970,
       title={Global Computation in a Poorly Connected World: Fast Rumor Spreading No Dependence on Conductance},
       author={Keren Censor-Hillel, Bernhard Haeupler, Jonathan Kelner, Petar Maymounkov},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2012},
       pages={961--970},
       doi={10.1145/2213977.2214064}}
            
     
     
212. Bounds on Contention Management in Radio Networks
     with Mohsen Ghaffari, Nancy Lynch, Calvin Newport
     DISC: International Symposium on Distributed Computing, 2012
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC12p237,
       title={Bounds on Contention Management in Radio Networks},
       author={Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, Calvin Newport},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2012},
       pages={223--237},
       doi={10.1007/978-3-642-33651-5_16}}
            
     
     
213. Lower Bounds on Information Dissemination in Dynamic Networks
     with Fabian Kuhn
     DISC: International Symposium on Distributed Computing, 2012
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC12p180,
       title={Lower Bounds on Information Dissemination in Dynamic Networks},
       author={Bernhard Haeupler, Fabian Kuhn},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2012},
       pages={166--180},
       doi={10.1007/978-3-642-33651-5_12}}
            
     
     
214. Bounded-Contention Coding for Wireless Networks in the High SNR Regime
     with Keren Censor-Hillel, Nancy Lynch, Muriel Medard
     DISC: International Symposium on Distributed Computing, 2012
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC12p105,
       title={Bounded-Contention Coding for Wireless Networks in the High SNR Regime},
       author={Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, Muriel Medard},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2012},
       pages={91--105},
       doi={10.1007/978-3-642-33651-5_7}}
            
     
     
215. Network Coded Gossip with Correlated Data
     with Asaf Cohen, Chen Avin, Muriel Medard
     ISIT: IEEE Internetional Symposium on Information Theory, 2012
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerISIT12p2620,
       title={Network Coded Gossip with Correlated Data},
       author={Bernhard Haeupler, Asaf Cohen, Chen Avin, Muriel Medard},
       journal={Proceeding of the IEEE Internetional Symposium on Information Theory (ISIT)},
       year={2012},
       pages={2616--2620},
       doi={10.1109/ISIT.2012.6283992}}
            
     
     
216. Discovery through Gossip
     with Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
     SPAA: ACM Symposium on Parallelism in Algorithms and Architectures, 2012
     (ArXiv)        (Download)        (ACM Authorizer Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSPAA12p149,
       title={Discovery through Gossip},
       author={Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun},
       journal={Proceeding of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
       year={2012},
       pages={140--149},
       doi={10.1145/2312005.2312031}}
            
     
     
217. Analyzing Network Coding Gossip Made Easy
     Bernhard Haeupler
     STOC: ACM Symposium on Theory of Computing, 2011
     Winner of the Danny Lewin Best Student Paper Award
     Invited to the SIAM Journal of Computing (SICOMP) Special Issue for STOC 2011
     Preliminary version presented at an invited session of the Allerton Conference (Allerton 2010)
     (ArXiv)        (Download)        (ACM Authorizer Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSTOC11p302,
       title={Analyzing Network Coding Gossip Made Easy},
       author={Bernhard Haeupler},
       journal={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
       year={2011},
       pages={293--302},
       doi={10.1145/1993636.1993676}}
            
     
     
218. Beeping a Maximal Independent Set
     with Noga Alon, Yehuda Afek, Ziv Bar-Joseph, Alejandro Cornejo, Fabian Kuhn
     DISC: International Symposium on Distributed Computing, 2011
     Invited to the Distributed Computing Special Issue for DISC 2011
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerDISC11p208,
       title={Beeping a Maximal Independent Set},
       author={Noga Alon, Yehuda Afek, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn},
       journal={Proceeding of the International Symposium on Distributed Computing (DISC)},
       year={2011},
       pages={195--208},
       doi={10.1007/978-3-642-24100-0_3}}
            
     
     
219. Faster Information Dissemination in Dynamic Networks via Network Coding
     with David Karger
     PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2011
     (ArXiv)        (Download)        (ACM Authorizer Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerPODC11p390,
       title={Faster Information Dissemination in Dynamic Networks via Network Coding},
       author={Bernhard Haeupler, David Karger},
       journal={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
       year={2011},
       pages={381--390},
       doi={10.1145/1993806.1993885}}
            
     
     
220. Optimality of Network Coding Buffers
     with Minji Kim, Muriel Medard
     ITW: IEEE Information Theory Workshop, 2011
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerITW11p537,
       title={Optimality of Network Coding Buffers},
       author={Bernhard Haeupler, Minji Kim, Muriel Medard},
       journal={Proceeding of the IEEE Information Theory Workshop (ITW)},
       year={2011},
       pages={533--537},
       doi={10.1109/ITW.2011.6089559}}
            
     
     
221. One Packet Suffices - Highly Efficient Network Coding Finite Memory
     with Muriel Medard
     ISIT: IEEE Internetional Symposium on Information Theory, 2011
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerISIT11p1155,
       title={One Packet Suffices - Highly Efficient Network Coding Finite Memory},
       author={Bernhard Haeupler, Muriel Medard},
       journal={Proceeding of the IEEE Internetional Symposium on Information Theory (ISIT)},
       year={2011},
       pages={1151--1155},
       doi={10.1109/ISIT.2011.6033713}}
            
     
     
222. Online Stochastic Weighted Matching: Improved Approximation Algorithms
     with Vahab Mirrokni, Morteza Zadimoghaddam
     WINE: Workshop on Internet and Economics, 2011
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerWINE11p181,
       title={Online Stochastic Weighted Matching: Improved Approximation Algorithms},
       author={Bernhard Haeupler, Vahab Mirrokni, Morteza Zadimoghaddam},
       journal={Proceeding of the Workshop on Internet and Economics (WINE)},
       year={2011},
       pages={170--181},
       doi={10.1007/978-3-642-25510-6_15}}
            
     
     
223. New Constructive Aspects of the Lovász Local Lemma
     with Barna Saha, Aravind Srinivasan
     FOCS: IEEE Symposium on Foundations of Computer Science, 2010
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerFOCS10p406,
       title={New Constructive Aspects of the Lovász Local Lemma},
       author={Bernhard Haeupler, Barna Saha, Aravind Srinivasan},
       journal={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
       year={2010},
       pages={397--406},
       doi={10.1109/FOCS.2010.45}}
            
     
     
224. Deterministic Algorithms for the Lovász Local Lemma
     with Karthekeyan Chandrasekaran, Navin Goyal
     SODA: ACM-SIAM Symposium on Discrete Algorithms, 2010
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerSODA10p2155,
       title={Deterministic Algorithms for the Lovász Local Lemma},
       author={Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler},
       journal={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
       year={2010},
       pages={2132--2155},
       doi={}}
            
     
     
225. Testing Simultaneous Planarity when the Common Graph is 2-Connected
     with Krishnam Raju Jampani, Anna Lubiw
     ISAAC: International Symposium on Algorithms and Computation, 2010
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerISAAC10p421,
       title={Testing Simultaneous Planarity when the Common Graph is 2-Connected},
       author={Bernhard Haeupler, Krishnam Raju Jampani, Anna Lubiw},
       journal={Proceeding of the International Symposium on Algorithms and Computation (ISAAC)},
       year={2010},
       pages={410--421},
       doi={10.1007/978-3-642-17514-5_35}}
            
     
     
226. Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive
     with William Garsarch
     CCR: International Conference on Logic, Computability and Randomness, 2010
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerCCR10p21,
       title={Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive},
       author={William Garsarch, Bernhard Haeupler},
       journal={Proceeding of the International Conference on Logic, Computability and Randomness (CCR)},
       year={2010},
       pages={1--21},
       doi={}}
            
     
     
227. Rank-Balanced Trees
     with Siddhartha Sen, Robert Tarjan
     WADS: Algorithms and Data Structures Symposium, 2010
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerWADS10p362,
       title={Rank-Balanced Trees},
       author={Bernhard Haeupler, Siddhartha Sen, Robert Tarjan},
       journal={Proceeding of the Algorithms and Data Structures Symposium (WADS)},
       year={2010},
       pages={351--362},
       doi={10.1007/978-3-642-03367-4_31}}
            
     
     
228. Rank-Pairing Heaps
     with Siddhartha Sen, Robert Tarjan
     ESA: European Symposium on Algorithms, 2009
     Invited to the Algorithmica Special Issue for ESA 2009
     (ArXiv)        (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerESA09p670,
       title={Rank-Pairing Heaps},
       author={Bernhard Haeupler, Siddhartha Sen, Robert Tarjan},
       journal={Proceeding of the European Symposium on Algorithms (ESA)},
       year={2009},
       pages={659--670},
       doi={10.1007/978-3-642-04128-0_59}}
            
     
     
229. Faster Algorithms for Incremental Topological Ordering
     with Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Tarjan
     ICALP: International Colloquium on Automata, Languages and Programming, 2008
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerICALP08p398,
       title={Faster Algorithms for Incremental Topological Ordering},
       author={Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Tarjan},
       journal={Proceeding of the International Colloquium on Automata, Languages and Programming (ICALP)},
       year={2008},
       pages={397--398},
       doi={10.1007/978-3-540-70575-8_35}}
            
     
     
230. Planarity Algorithms via PQ-trees (Extended Abstract)
     with Robert Tarjan
     TGGT: Topological & Geometric Graph Theory International Conference, 2008
     Invited to the European Journal of Combinatorics Special Issue for TGGT 2008
     (Download)        
     (BibTex)(Hide BibTex)

     • @article{HaeuplerTGGT08p149,
       title={Planarity Algorithms via PQ-trees (Extended Abstract)},
       author={Bernhard Haeupler, Robert Tarjan},
       journal={Proceeding of the Topological & Geometric Graph Theory International Conference (TGGT)},
       year={2008},
       pages={143--149},
       doi={10.1016/j.endm.2008.06.029}}
            
     
     

Journal Publications