Bernhard Haeupler

Address

MIT Computer Science and Artificial Intelligence Lab
32-G678, Stata Center
32 Vassar Street
Cambridge, MA 02139
USA

email: haeupler at mit.edu
tel: (617) 253-5866
voice-box: (617) 715-2586

Map showing building location.

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 will spend June at Microsoft Research New England and then join Microsoft Research Silicon Valley for a year.
In 2014 I will join the faculty of the Department of Computer Science at Carnegie Mellon University.

In 2010 I completed the Masters of Science in EECS at MIT. 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 Diplom in Mathematics, the TopMath Bachelor of Science and the TopMath Master of Science with Honours.

Recent Activities:

01-04-2013 Invited Talk at Microsoft Research New England (Video)

01-07-2013 Best Student Paper Award at SODA 2013 (Paper)

01-10-2013 MIT News reports on the paper "Simple, Fast and Determinstic Gossip" (Link 1, Link 2)

01-10-2013 Invited Talk at Microsoft Research Silicon Valley

01-14-2013 Invited Talk at UIUC

01-18-2013 Invited Talk at the Max-Planck Institute for Informatics, Germany

01-20-2013 Presentation at the Dagstuhl Workshop on "Epidemic Algorithms and Processes" (Link)

02-13-2013 Representing MIT on the ITA Graduation Day with the presentation "Analyzing Network Coding Gossip Made Easy" (Link)

02-22-2013 Presentation at the Theory Graduating Student Day at MIT (Link)

03-18-2013 Invited Talk at CMU

04-18-2013 Thesis Defense

05-22-2013 Thesis Submitted

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.

Conference Publications

Broadcast in Radio Networks with Collision Detection
with Mohsen Ghaffari, Majid Khabbazian
PODC: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, 2013
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
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
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 (DIST) 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

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) (PDF)
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

A Bound on the Throughput of Radio Networks
with Mohsen Ghaffari, Majid Khabbazian
ArXiv: ArXiv.org e-Print, 2013
(ArXiv)
Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections
with Karthekeyan Chandrasekaran, Navin Goyal
ArXiv: ArXiv.org e-Print, 2010
(ArXiv)
Robust Regulatory Networks
with Arnab Bhattacharyya
ArXiv: ArXiv.org e-Print, 2009
(ArXiv)

Random Stuff

Journals I reviewed for:
Journal of the ACM (JACM),
SIAM Journal on Computing (SICOMP),
Transactions of Information Theory (TransInf),
Transactions on Algorithms (TransAlg),
Distributed Computing (DIST),
Random Structures & Algorithms (RSA),
Transactions on Communications (TCOM),
Transactions on Computers (TC),
Information Processing Letters (IPL),
Communications Letters (CL),
Software, Practice and Experience (SPE)
Conferences I reviewed for:
Symposium on Theory of Computation (STOC),
Foundations of Computer Science (FOCS),
Symposium on Discrete Algorithms (SODA),
Principles of Distributed Computing (PODC),
International Symposium on Information Theory (ISIT),
International Colloquium on Automata, Languages and Programming (ICALP),
Symposium on Parallelism in Algorithms and Architectures (SPAA),
Distributed Computing (DISC),
Allerton Conference on Communication Control and Computing (Allerton),
Information Theory Workshop (ITW),
European Symposium on Algorithms (ESA),
Innovations in Computer Science (I(T)CS),
Mathematical Foundations of Computer Science (MFCS),
Algorithms Engineering and Experiments (ALENEX),
Theory and Practice of Algorithms in (Computer) Systems (TAPAS),
Fun with Algorithms (FUN)
I was lucky to collaborate and publish together with these wonderful researchers:
Alejandro Cornejo, Anna Lubiw, Aravind Srinivasan, Arnab Bhattacharyya, Asaf Cohen, Barna Saha, Calvin Newport, Chen Avin, Christian Scheideler, David Peleg, David R. Karger, Fabian Kuhn, Gopal Pandurangan, Jonathan A. Kelner, Karthekeyan Chandrasekaran, Keren Censor-Hillel, Krishnam Raju Jampani, Majid Khabbazian, Michael Borokhovich, MinJi Kim, Mohsen Ghaffari, Morteza Zadimoghaddam, Muriel Médard, Nancy Lynch, Navin Goyal, Noga Alon, Petar Maymounkov, Rajmohan Rajaraman, Robert Endre Tarjan, Rogers Mathew, Siddhartha Sen, Stefan Schmid, Telikepalli Kavitha, Vahab S. Mirrokni, William I. Gasarch, Yehuda Afek, Zhifeng Sun, Ziv Bar-Joseph, Zvi Lotker
My Erdoes number is 2 via Noga Alon (and I suppose always will be).