Bernhard Haeupler
Assistant Professor of Computer Science, CMU

Haeupler Address / Contact Information:

School of Computer Science
Carnegie Mellon University
Pittsburgh PA 15213-3891

Office: 7005 Gates Hillman Center
Tel: +1 (412) 268-3984
Email: haeupler at cs.cmu.edu

Administrative Assistant:

Melissa Keaton
Office: 7227 Gates Hillman Center
Tel: +1 (412) 268-7932
Email: melissa at cs.cmu.edu


Publications

Research Interests:

I am a theoretical computer scientist working on the design and analysis of algorithms for combinatorial problems. I particularly like to work on problems in distributed computing and use the power of randomization. Much of my work intermixes these classical topics with questions, ideas, and tools from (network) coding theory, and information theory.
Most recently I got particularly interested in error correcting coding schemes for interactive communications and distributed network optimization algorithms.

Current Students:    David Wajc, Amirbehshad Shahrasbi, Nicolas Resch, Goran Zuzic
I am looking forward to taking on more students. Come and talk to me!

Recent Activities and News: Courses:

Currently: 15-251 Great Theoretical Ideas in Computer Science
F15: 15-859-Z Algorithmic Superpower Randomization
F14: 15-859-Z Algorithmic Superpower Randomization

Conference Publications

  1. Constant-rate coding for multiparty interactive communication is impossible
    with Mark Braverman, Klim Efremenko, Ran Gelles
    STOC: ACM Symposium on Theory of Computing, 2016


  2. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2016},
      pages={202--219},
      doi={10.1137/1.9781611974331.ch16}}
           

  3. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2016},
      pages={1922--1936},
      doi={10.1137/1.9781611974331.ch135}}
           

  4. 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},
      inproceedings={Proceeding of the International Workshop on Randomization and Computation (RANDOM)},
      year={2015},
      pages={881--897},
      doi={10.4230/LIPIcs.APPROX-RANDOM.2015.881}}
           

  5. 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},
      inproceedings={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
      year={2015},
      pages={413--419},
      doi={10.1145/2767386.2767435}}
           

  6. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2015},
      pages={2006--2018},
      doi={10.1137/1.9781611973730.133}}
           

  7. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2015},
      pages={1296--1311},
      doi={10.1137/1.9781611973730.86}}
           

  8. 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
    (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},
      inproceedings={Proceeding of the ACM-SIGACT Innovations in Theoretical Computer Science Conference (ITCS)},
      year={2015},
      pages={11--20},
      doi={10.1145/2688073.2688077}}
           

  9. 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},
      inproceedings={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
      year={2014},
      pages={226--235},
      doi={10.1109/FOCS.2014.32}}
           

  10. 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},
      inproceedings={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
      year={2014},
      pages={394--403},
      doi={10.1109/FOCS.2014.49}}
           

  11. 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},
      inproceedings={Proceeding of the IEEE Information Theory Workshop (ITW)},
      year={2014},
      pages={152--156},
      doi={10.1109/ITW.2014.6970811}}
           

  12. 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},
      inproceedings={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
      year={2014},
      pages={114--123},
      doi={10.1145/2611462.2611469}}
           

  13. 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},
      inproceedings={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
      year={2014},
      pages={176--185},
      doi={10.1145/2611462.2611489}}
           

  14. 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},
      inproceedings={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
      year={2014},
      pages={794--803},
      doi={10.1145/2591796.2591872}}
           

  15. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2014},
      pages={1831--1843},
      doi={10.1137/1.9781611973402.132}}
           

  16. 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},
      inproceedings={Proceeding of the International Symposium on Distributed Computing (DISC)},
      year={2013},
      pages={492--506},
      doi={10.1007/978-3-642-41527-2_34}}
           

  17. 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},
      inproceedings={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
      year={2013},
      pages={325--334},
      doi={10.1145/2484239.2484248}}
           

  18. Simple, Fast, and Deterministic Gossip and Rumor Spreading
    Bernhard Haeupler
    SODA: ACM-SIAM Symposium on Discrete Algorithms, 2013
    Winner of the SODA‘13 Best Student Paper Award
    (ArXiv)        (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerSODA13p716,
      title={Simple, Fast, and Deterministic Gossip and Rumor Spreading},
      author={Bernhard Haeupler},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2013},
      pages={705--716},
      doi={}}
           

  19. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2013},
      pages={748--766},
      doi={}}
           

  20. 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},
      inproceedings={Proceeding of the IEEE International Parallel and Distributed Processing Symposium (IPDPS)},
      year={2013},
      pages={395--406},
      doi={10.1109/IPDPS.2013.40}}
           

  21. 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},
      inproceedings={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}}
           

  22. 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},
      inproceedings={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
      year={2012},
      pages={961--970},
      doi={10.1145/2213977.2214064}}
           

  23. 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},
      inproceedings={Proceeding of the International Symposium on Distributed Computing (DISC)},
      year={2012},
      pages={223--237},
      doi={10.1007/978-3-642-33651-5_16}}
           

  24. 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},
      inproceedings={Proceeding of the International Symposium on Distributed Computing (DISC)},
      year={2012},
      pages={166--180},
      doi={10.1007/978-3-642-33651-5_12}}
           

  25. Bounded-Contention Coding for Wireless Networks in the High SNR Regime
    with Keren Censor-Hillel, Nancy Lynch, Muriel Médard
    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 Médard},
      inproceedings={Proceeding of the International Symposium on Distributed Computing (DISC)},
      year={2012},
      pages={91--105},
      doi={10.1007/978-3-642-33651-5_7}}
           

  26. Network Coded Gossip with Correlated Data
    with Asaf Cohen, Chen Avin, Muriel Médard
    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 Médard},
      inproceedings={Proceeding of the IEEE Internetional Symposium on Information Theory (ISIT)},
      year={2012},
      pages={2616--2620},
      doi={10.1109/ISIT.2012.6283992}}
           

  27. 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},
      inproceedings={Proceeding of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
      year={2012},
      pages={140--149},
      doi={10.1145/2312005.2312031}}
           

  28. 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},
      inproceedings={Proceeding of the ACM Symposium on Theory of Computing (STOC)},
      year={2011},
      pages={293--302},
      doi={10.1145/1993636.1993676}}
           

  29. 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},
      inproceedings={Proceeding of the International Symposium on Distributed Computing (DISC)},
      year={2011},
      pages={195--208},
      doi={10.1007/978-3-642-24100-0_3}}
           

  30. 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},
      inproceedings={Proceeding of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
      year={2011},
      pages={381--390},
      doi={10.1145/1993806.1993885}}
           

  31. Optimality of Network Coding Buffers
    with Minji Kim, Muriel Médard
    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 Médard},
      inproceedings={Proceeding of the IEEE Information Theory Workshop (ITW)},
      year={2011},
      pages={533--537},
      doi={10.1109/ITW.2011.6089559}}
           

  32. One Packet Suffices - Highly Efficient Network Coding Finite Memory
    with Muriel Médard
    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 Médard},
      inproceedings={Proceeding of the IEEE Internetional Symposium on Information Theory (ISIT)},
      year={2011},
      pages={1151--1155},
      doi={10.1109/ISIT.2011.6033713}}
           

  33. 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},
      inproceedings={Proceeding of the Workshop on Internet and Economics (WINE)},
      year={2011},
      pages={170--181},
      doi={10.1007/978-3-642-25510-6_15}}
           

  34. 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},
      inproceedings={Proceeding of the IEEE Symposium on Foundations of Computer Science (FOCS)},
      year={2010},
      pages={397--406},
      doi={10.1109/FOCS.2010.45}}
           

  35. 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},
      inproceedings={Proceeding of the ACM-SIAM Symposium on Discrete Algorithms (SODA)},
      year={2010},
      pages={2132--2155},
      doi={}}
           

  36. 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},
      inproceedings={Proceeding of the International Symposium on Algorithms and Computation (ISAAC)},
      year={2010},
      pages={410--421},
      doi={10.1007/978-3-642-17514-5_35}}
           

  37. 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},
      inproceedings={Proceeding of the International Conference on Logic, Computability and Randomness (CCR)},
      year={2010},
      pages={1--21},
      doi={}}
           

  38. 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},
      inproceedings={Proceeding of the Algorithms and Data Structures Symposium (WADS)},
      year={2010},
      pages={351--362},
      doi={10.1007/978-3-642-03367-4_31}}
           

  39. 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},
      inproceedings={Proceeding of the European Symposium on Algorithms (ESA)},
      year={2009},
      pages={659--670},
      doi={10.1007/978-3-642-04128-0_59}}
           

  40. 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},
      inproceedings={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}}
           

  41. 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},
      inproceedings={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

  1. Analyzing Network Coding (Gossip) Made Easy
    Bernhard Haeupler
    JACM: Journal of the ACM, 2016


  2. Discovery through Gossip
    with Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
    RSA: Random Structures and Algorithms, 2016
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerRSA16p587,
      title={Discovery through Gossip},
      author={Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun},
      inproceedings={Random Structures and Algorithms (RSA)},
      year={2016},
      pages={565--587},
      doi={10.1002/rsa.20621}}
           

  3. Simple, Fast, and Deterministic Gossip and Rumor Spreading
    Bernhard Haeupler
    JACM: Journal of the ACM, 2015
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerJACM15p47:18,
      title={Simple, Fast, and Deterministic Gossip and Rumor Spreading},
      author={Bernhard Haeupler},
      inproceedings={Journal of the ACM (JACM)},
      year={2015},
      pages={47:1--47:18},
      doi={10.1145/2767126}}
           

  4. Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited, and Anonymous Communication
    with Ofer Feinerman, Amos Korman
    DIST: Distributed Computing, 2015
    Invited to the Distributed Computing Special Issue for PODC 2014
    (ArXiv)        (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerDIST15p123,
      title={Breathe before Speaking: Efficient Information Dissemination despite Noisy, Limited, and Anonymous Communication},
      author={Ofer Feinerman, Bernhard Haeupler, Amos Korman},
      inproceedings={Distributed Computing (DIST)},
      year={2015},
      pages={114--123},
      doi={10.1145/2611462.2611469}}
           

  5. Rank-Balanced Trees
    with Siddhartha Sen, Robert Tarjan
    TALG: ACM Transactions on Algorithms, 2015
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerTALG15p26,
      title={Rank-Balanced Trees},
      author={Bernhard Haeupler, Siddhartha Sen, Robert Tarjan},
      inproceedings={ACM Transactions on Algorithms (TALG)},
      year={2015},
      pages={1--26},
      doi={10.1145/2689412}}
           

  6. SplayNet: Towards Locally Self-Adjusting Networks
    with Stefan Schmid, Chen Avin, Scheideler Christian, Michael Borokhovich, Zvi Loetker
    ToN: IEEE/ACM Transactions on Networking, 2015
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerToN15p13,
      title={SplayNet: Towards Locally Self-Adjusting Networks},
      author={Stefan Schmid, Chen Avin, Scheideler Christian, Bernhard Haeupler, Michael Borokhovich, Zvi Loetker},
      inproceedings={IEEE/ACM Transactions on Networking (ToN)},
      year={2015},
      pages={1--13},
      doi={10.1109/TNET.2015.2410313 }}
           

  7. Bounded-Contention Coding for the Additive Network Model
    with Keren Censor-Hillel, Nancy Lynch, Muriel Médard
    DIST: Distributed Computing, 2015
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerDIST15p12,
      title={Bounded-Contention Coding for the Additive Network Model},
      author={Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, Muriel Médard},
      inproceedings={Distributed Computing (DIST)},
      year={2015},
      pages={1--12},
      doi={10.1007/s00446-015-0244-9}}
           

  8. Self-Adjusting Grid Networks to Minimize Expected Path Length
    with Chen Avin, Michael Borokhovich, Zvi Loetker
    TCS: Theoretical Computer Science, 2014
    Special Issue for SIROCCO 2013
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerTCS14p102,
      title={Self-Adjusting Grid Networks to Minimize Expected Path Length},
      author={Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Loetker},
      inproceedings={Theoretical Computer Science (TCS)},
      year={2014},
      pages={91--102},
      doi={10.1016/j.tcs.2014.11.036}}
           

  9. Network Coding Based Information Spreading in Dynamic Networks with Correlated Data
    with Asaf Cohen, Chen Avin, Muriel Médard
    JSAC: IEEE Journal on Selected Areas in Communications, 2014
    Special Issue on Network Coding in Wireless Communications
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerJSAC14p224,
      title={Network Coding Based Information Spreading in Dynamic Networks with Correlated Data},
      author={Asaf Cohen, Bernhard Haeupler, Chen Avin, Muriel Médard},
      inproceedings={IEEE Journal on Selected Areas in Communications (JSAC)},
      year={2014},
      pages={213--224},
      doi={10.1109/JSAC.2014.2384293}}
           

  10. Randomized Broadcast in Radio Networks with Collision Detection
    with Mohsen Ghaffari, Majid Khabbazian
    DIST: Distributed Computing, 2014
    Special Issue for PODC 2013
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerDIST14p16,
      title={Randomized Broadcast in Radio Networks with Collision Detection},
      author={Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian},
      inproceedings={Distributed Computing (DIST)},
      year={2014},
      pages={1--16},
      doi={10.1007/s00446-014-0230-7}}
           

  11. Deterministic Algorithms for the Lovász Local Lemma
    with Karthekeyan Chandrasekaran, Navin Goyal
    SICOMP: SIAM Journal on Computing, 2013
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerSICOMP13p2155,
      title={Deterministic Algorithms for the Lovász Local Lemma},
      author={Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler},
      inproceedings={SIAM Journal on Computing (SICOMP)},
      year={2013},
      pages={2132--2155},
      doi={10.1137/100799642}}
           

  12. Testing Simultaneous Planarity when the Common Graph is 2-Connected
    with Krishnam Raju Jampani, Anna Lubiw
    JGAA: Journal on Graph Algorithms and Applications, 2013
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerJGAA13p171,
      title={Testing Simultaneous Planarity when the Common Graph is 2-Connected},
      author={Krishnam Raju Jampani, Bernhard Haeupler, Anna Lubiw},
      inproceedings={Journal on Graph Algorithms and Applications (JGAA)},
      year={2013},
      pages={147--171},
      doi={10.7155/jgaa.00289}}
           

  13. Beeping a Maximal Independent Set
    with Noga Alon, Yehuda Afek, Ziv Bar-Joseph, Alejandro Cornejo, Fabian Kuhn
    DIST: Distributed Computing, 2013
    Special Issue for DISC 2011
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerDIST13p208,
      title={Beeping a Maximal Independent Set},
      author={Noga Alon, Yehuda Afek, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn},
      inproceedings={Distributed Computing (DIST)},
      year={2013},
      pages={195--208},
      doi={10.1007/s00446-012-0175-7}}
           

  14. New Constructive Aspects of the Lovász Local Lemma
    with Barna Saha, Aravind Srinivasan
    JACM: Journal of the ACM, 2012
    (Download)        (ACM Authorizer Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerJACM12p28:28,
      title={New Constructive Aspects of the Lovász Local Lemma},
      author={Bernhard Haeupler, Barna Saha, Aravind Srinivasan},
      inproceedings={Journal of the ACM (JACM)},
      year={2012},
      pages={28:1--28:28},
      doi={10.1145/2049697.2049702}}
           

  15. Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
    with Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Tarjan
    TALG: ACM Transactions on Algorithms, 2012
    (Download)        (ACM Authorizer Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerTALG12p3:33,
      title={Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance},
      author={Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Tarjan},
      inproceedings={ACM Transactions on Algorithms (TALG)},
      year={2012},
      pages={3:1--3:33},
      doi={10.1145/2071379.2071382}}
           

  16. Rank-Pairing Heaps
    with Siddhartha Sen, Robert Tarjan
    SICOMP: SIAM Journal on Computing, 2011
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerSICOMP11p1485,
      title={Rank-Pairing Heaps},
      author={Bernhard Haeupler, Siddhartha Sen, Robert Tarjan},
      inproceedings={SIAM Journal on Computing (SICOMP)},
      year={2011},
      pages={1463--1485},
      doi={10.1137/100785351}}
           

  17. Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive
    with William Garsarch
    COMBINATORICS: Electronic Journal on Combinatorics, 2011
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerCOMBINATORICS11p21,
      title={Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive},
      author={William Garsarch, Bernhard Haeupler},
      inproceedings={Electronic Journal on Combinatorics (COMBINATORICS)},
      year={2011},
      pages={1--21},
      doi={}}
           

Letters and Brief Announcements

  1. Near-Optimal BFS Computation in Radio Networks
    with Mohsen Ghaffari
    CL: IEEE Communications Letter, 2016


  2. Tighter Worst-Case Bounds on Algebraic Gossip
    Bernhard Haeupler
    CL: IEEE Communications Letter, 2012
    (ArXiv)        (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerCL12p1276,
      title={Tighter Worst-Case Bounds on Algebraic Gossip},
      author={Bernhard Haeupler},
      inproceedings={IEEE Communications Letter (CL)},
      year={2012},
      pages={1274--1276},
      doi={10.1109/LCOMM.2012.060112.120632}}
           

  3. SplayNets: Towards Self-Adjusting Distributed Data Structures
    with Chen Avin, Michael Borokhovich, Zvi Loetker, Christian Scheideler, Stefan Schmid
    DISC Brief Announcement: International Symposium on Distributed Computing, 2012
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerDISC Brief Announcement12p440 ,
      title={SplayNets: Towards Self-Adjusting Distributed Data Structures},
      author={Chen Avin, Michael Borokhovich, Bernhard Haeupler, Zvi Loetker, Christian Scheideler, Stefan Schmid},
      inproceedings={International Symposium on Distributed Computing (DISC Brief Announcement)},
      year={2012},
      pages={439--440 },
      doi={10.1007/978-3-642-33651-5_47}}
           

  4. Finding a Feasible Flow in a Strongly Connected Network
    with Robert Tarjan
    ORL: Operations Research Letters, 2008
    (ArXiv)        (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerORL08p398,
      title={Finding a Feasible Flow in a Strongly Connected Network},
      author={Bernhard Haeupler, Robert Tarjan},
      inproceedings={Operations Research Letters (ORL)},
      year={2008},
      pages={397--398},
      doi={10.1016/j.orl.2008.02.003}}
           

Patent Applications

  1. Method and Apparatus for Performing Finite Memory Network Coding in an Arbitrary Network
    with Muriel Médard
    Patent: US Utility Patent Application, 2015
    patent pending (continuation application)


  2. Node Identification using Clusters
    with Dahlia Malkhi
    Patent: US Utility Patent Application, 2014
    patent pending


  3. Error Correction for Interactive Message Exchanges Using Summaries
    Bernhard Haeupler
    Patent: US Utility Patent Application, 2014
    patent pending


  4. Generating unweighted samples from weighted samples
    with Mark Manasse, Kunal Talwar
    Patent: US Utility Patent Application, 2014
    patent pending


  5. Method and Apparatus for Performing Finite Memory Network Coding in an Arbitrary Network
    with Muriel Médard
    Patent: US Utility Patent Application, 2013
    patent to be issued (published as US20140064296)
    (Download)        

Other Manuscripts

  1. Reliable Communication over Highly Connected Noisy Networks
    with Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles
    ECC: Electronic Colloquium on Computational Complexity, 2015
    (Download)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerECC15p17,
      title={Reliable Communication over Highly Connected Noisy Networks},
      author={Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler},
      inproceedings={Electronic Colloquium on Computational Complexity (ECC)},
      year={2015},
      pages={1--17},
      doi={}}
           

  2. Consistent Weighted Sampling Made Fast, Small, and Easy
    with Kunal Talwar, Mark Manasse
    ArXiv: ArXiv.org e-Print, 2014
    (ArXiv)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerArXiv14p18,
      title={Consistent Weighted Sampling Made Fast, Small, and Easy},
      author={Bernhard Haeupler, Kunal Talwar, Mark Manasse},
      inproceedings={ArXiv.org e-Print (ArXiv)},
      year={2014},
      pages={1--18},
      doi={}}
           

  3. Probabilistic Methods for Distributed Information Dissemination
    Bernhard Haeupler
    PhD Thesis: MIT, 2013
    Winner of the ACM-EATCS Doctoral Dissertation Award in Distributed Computing 2014
    Awarded with a George M. Sprowls Award for Outstanding Theses in Computer Science

    (BibTex)(Hide BibTex)
    • @article{HaeuplerPhD Thesis13p484,
      title={Probabilistic Methods for Distributed Information Dissemination},
      author={Bernhard Haeupler},
      inproceedings={MIT (PhD Thesis)},
      year={2013},
      pages={1--484},
      doi={}}
           

  4. A Bound on the Throughput of Radio Networks
    with Mohsen Ghaffari, Majid Khabbazian
    ArXiv: ArXiv.org e-Print, 2013
    (ArXiv)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerArXiv13p3,
      title={A Bound on the Throughput of Radio Networks},
      author={Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian},
      inproceedings={ArXiv.org e-Print (ArXiv)},
      year={2013},
      pages={1--3},
      doi={}}
           

  5. Robust Regulatory Networks
    with Arnab Bhattacharyya
    ArXiv: ArXiv.org e-Print, 2009
    (ArXiv)        
    (BibTex)(Hide BibTex)
    • @article{HaeuplerArXiv09p23,
      title={Robust Regulatory Networks},
      author={Arnab Bhattacharyya, Bernhard Haeupler},
      inproceedings={ArXiv.org e-Print (ArXiv)},
      year={2009},
      pages={1--23},
      doi={}}
           

Random Stuff