Bernhard Haeupler

Haeupler

Address

Microsoft Research
1065 La Avenida
Mountain View, CA 94043
USA

email: haeupler at cs.cmu.edu
tel: (650) 693-0214

Bernhard Haeupler

I recently completed my PhD at the Theory Group of the MIT Computer Science Department where I was advised by Jonathan Kelner, Muriel Médard and David Karger.

I am currently a postdoc at Microsoft Research Silicon Valley and in 2014 I will join the faculty of the Department of Computer Science at Carnegie Mellon University.

Before I came to MIT I spent a year visiting the Theory Group of the Princeton University Computer Science Department where I worked with Robert E. Tarjan. I did my undergraduate studies at the Technical University Munich in Germany where I studied Mathematics and was a fellow of TopMath. I graduated with a Diploma in Mathematics, the TopMath Bachelor of Science, and the TopMath Master of Science with Honours.

Recent News:

  • My thesis "Probabilistic Methods for Distributed Information Dissemination" was one of two theses awarded with a George Sprowls Award for an outstanding PhD thesis in Computer Science and Electrical Engineering.
  • MIT nominated my thesis for the ACM Doctoral Dissertation Award
  • I am on the program comitte of the 2014 International Conference on Distributed Computing (DISC)

    Research Interests

    I am interested in theoretical computer science, especially the design and analysis of algorithms for combinatorial problems.
    Lately, I have mixed this classical area with ideas from information and (network) coding theory, networking and distributed computing.
    In particular, I designed novel efficient solutions to various information dissemination problems using coding and gossip approaches.
    I have also worked on classical data structures, planarity tests and algorithmic applications of the Lovasz Local Lemma.
    Most recently I got very interested in error correcting coding schemes for interactive communications.

    Selected Recent Manuscripts

    • Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
      with Mohsen Ghaffari
      (ArXiv)        

    • 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)        

    Conference Publications

    • 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
      (ArXiv)        

    • Optimal Gossip With Direct Addressing
      with Dahlia Malkhi
      PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2014
      (ArXiv)        

    • 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)        

    • Broadcast Throughput in Radio Networks: Routing vs. Network Coding
      with Noga Alon, Mohsen Ghaffari, Majid Khabbazian
      SODA: ACM-SIAM Symposium on Discrete Algorithms, 2014
      (Download)        (ArXiv)        

    • Fast Structuring of Radio Networks for Multi-Message Communications
      with Mohsen Ghaffari
      DISC: International Symposium on Distributed Computing, 2013
      (Download)        (ArXiv)        

    • 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
      (Download)        (ArXiv)        

    • 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
      (Download)        (ArXiv)        

    • Near Optimal Leader Election in Multi-Hop Radio Networks
      with Mohsen Ghaffari
      SODA: ACM-SIAM Symposium on Discrete Algorithms, 2013
      (Download)        (ArXiv)        

    • 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)        

    • 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
      (Download)        (ArXiv)        

    • 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
      (Download)        (ArXiv)        (ACM Authorizer Download)        

    • Bounds on Contention Management in Radio Networks
      with Mohsen Ghaffari, Nancy Lynch, Calvin Newport
      DISC: International Symposium on Distributed Computing, 2012
      (Download)        (ArXiv)        

    • Lower Bounds on Information Dissemination in Dynamic Networks
      with Fabian Kuhn
      DISC: International Symposium on Distributed Computing, 2012
      (Download)        (ArXiv)        

    • 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
      (Download)        (ArXiv)        

    • Network Coded Gossip with Correlated Data
      with Asaf Cohen, Chen Avin, Muriel Médard
      ISIT: IEEE Internetional Symposium on Information Theory, 2012
      (Download)        (ArXiv)        

    • Discovery through Gossip
      with Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun
      SPAA: ACM Symposium on Parallelism in Algorithms and Architectures, 2012
      (Download)        (ArXiv)        (ACM Authorizer Download)        

    • 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)
      (Download)        (ArXiv)        (ACM Authorizer Download)        

    • 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
      (Download)        (ArXiv)        

    • Faster Information Dissemination in Dynamic Networks via Network Coding
      with David Karger
      PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2011
      (Download)        (ArXiv)        (ACM Authorizer Download)        

    • Optimality of Network Coding Buffers
      with Minji Kim, Muriel Médard
      ITW: IEEE Information Theory Workshop, 2011
      (Download)        (ArXiv)        

    • One Packet Suffices - Highly Efficient Network Coding Finite Memory
      with Muriel Médard
      ISIT: IEEE Internetional Symposium on Information Theory, 2011
      (Download)        (ArXiv)        

    • Online Stochastic Weighted Matching: Improved Approximation Algorithms
      with Vahab Mirrokni, Morteza Zadimoghaddam
      WINE: Workshop on Internet and Economics, 2011
      (Download)        

    • New Constructive Aspects of the Lovász Local Lemma
      with Barna Saha, Aravind Srinivasan
      FOCS: IEEE Symposium on Foundations of Computer Science, 2010
      (Download)        (ArXiv)        

    • Deterministic Algorithms for the Lovász Local Lemma
      with Karthekeyan Chandrasekaran, Navin Goyal
      SODA: ACM-SIAM Symposium on Discrete Algorithms, 2010
      (Download)        (ArXiv)        

    • Testing Simultaneous Planarity when the Common Graph is 2-Connected
      with Krishnam Raju Jampani, Anna Lubiw
      ISAAC: International Symposium on Algorithms and Computation, 2010
      (Download)        (ArXiv)        

    • Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive
      with William Garsarch
      CCR: International Conference on Logic, Computability and Randomness, 2010
      (Download)        (ArXiv)        

    • Rank-Balanced Trees
      with Siddhartha Sen, Robert Tarjan
      WADS: Algorithms and Data Structures Symposium, 2010
      (Download)        

    • Rank-Pairing Heaps
      with Siddhartha Sen, Robert Tarjan
      ESA: European Symposium on Algorithms, 2009
      Invited to the Algorithmica Special Issue for ESA 2009
      (Download)        (ArXiv)        

    • Faster Algorithms for Incremental Topological Ordering
      with Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert E. Tarjan
      ICALP: International Colloquium on Automata, Languages and Programming, 2008
      (Download)        

    • 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)        

    Journal Publications

    • Deterministic Algorithms for the Lovász Local Lemma
      with Karthekeyan Chandrasekaran, Navin Goyal
      SICOMP: SIAM Journal on Computing, 2013
      (Download)        

    • 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)        

    • 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)        

    • New Constructive Aspects of the Lovász Local Lemma
      with Barna Saha, Aravind Srinivasan
      JACM: Journal of the ACM, 2012
      (Download)        (ACM Authorizer Download)        

    • Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
      with Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert E. Tarjan
      TALG: ACM Transactions on Algorithms, 2012
      (Download)        (ACM Authorizer Download)        

    • Rank-Pairing Heaps
      with Siddhartha Sen, Robert E. Tarjan
      SICOMP: SIAM Journal on Computing, 2011
      (Download)        

    • Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive
      with William Garsarch
      COMBINATORICS: Electronic Journal on Combinatorics, 2011
      (Download)        

    Letters and Brief Announcements

    • Tighter Worst-Case Bounds on Algebraic Gossip
      Bernhard Haeupler
      CL: IEEE Communications Letter, 2012
      (Download)        (ArXiv)        

    • 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)        

    • Finding a Feasible Flow in a Strongly Connected Network
      with Robert Tarjan
      ORL: Operations Research Letters, 2008
      (Download)        (ArXiv)        

    Patent Applications

    • Method and Apparatus for Performing Finite Memory Network Coding
      with Muriel Médard
      U.S. Appl. No.: 13/761,799

    Other Manuscripts

    • Probabilistic Methods for Distributed Information Dissemination
      Bernhard Haeupler
      PhD Thesis: MIT, 2013
      Awarded with an George M. Sprowls Award for outstanding theses in computer science
      Nominated by MIT for the ACM Doctoral Dissertation Award


    • A Bound on the Throughput of Radio Networks
      with Mohsen Ghaffari, Majid Khabbazian
      ArXiv: ArXiv.org e-Print, 2013
      (ArXiv)        

    • Robust Regulatory Networks
      with Arnab Bhattacharyya
      ArXiv: ArXiv.org e-Print, 2009
      (ArXiv)        

    Random Stuff