Christoph Lenzen Computer Sciene and Artificial Intelligence Laboratory (CSAIL) Massachusetts Institute of Technology (MIT) The Stata Center 32 Vassar Street, office 32-G666 Cambridge, MA 02139, USA Email: clenzen@csail.mit.edu Phone: +1 617 253 4623

This page is no longer maintained. Please visit my new homepage!

Research Interests:

Theory of Distributed Computing, in particular clock synchronization, randomized load balancing, routing, graph problems (e.g. dominating sets, maximal independent sets, coloring), and fault-tolerance. Check out this poster about fault-tolerant clock synchronization!

---

Short CV:

since July 2014: Group Leader at MPI Saarbruecken, Department for Algorithms and Complexity.
2013 - June 2014: Postdoctoral fellow at MIT CSAIL, with Nancy Lynch.
2012: Postdoctoral fellow in the Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, with David Peleg.
2011: Postdoctoral fellow in the Department of Computer Science and Engineering, Hebrew University of Jerusalem, with Danny Dolev.
2011: Ph.D. degree from ETH Zurich. Thesis: Synchronization and Symmetry Breaking in Distributed Systems.
2007-2010: Graduate studies, Distributed Computing Group, ETH Zurich. My advisor was Roger Wattenhofer.
2007: Diploma Degree in Mathematics, University of Bonn.

---

Publications:

• Tight Bounds for Parallel Randomized Load Balancing
  Christoph Lenzen and Roger Wattenhofer.
  Distributed Computing, to appear.
  preprint
• Improved Distributed Steiner Forest Construction
  Christoph Lenzen and Boaz Patt-Shamir.
  33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
  arxiv
• Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
  Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva.
  33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
  arxiv
• Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs
  Miikka Hilke, Christoph Lenzen, and Jukka Suomela
  33rd Symposium on Principles of Distributed Computing (PODC), July 2014.
  
• PulseSync: An Efficient and Scalable Clock Synchronization Protocol
  Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
  Transactions on Networking, to appear.
  preprint
• Fault-tolerant Algorithms for Tick-generation in Asynchronous Logic: Robust Pulse Generation
  Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
  Journal of the ACM, to appear.
  preprint
• Rigorously Modeling Self-Stabilizing Fault-Tolerant Circuits: An Ultra-Robust Clocking Scheme for Systems-on-Chip
  Danny Dolev, Matthias Fuegger, Christoph Lenzen, Markus Posch, Ulrich Schmid, and Andreas Steininger.
  Journal of Computer and System Sciences, 80(4):860-900.
  
• Synchronous Counting and Computational Algorithm Design
  Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
  15th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2013.
  
• The Power of Pheromones in Ant Foraging
  Christoph Lenzen and Tsvetomira Radeva.
  1st Workshop on Biological Distributed Algorithms (BDA), October 2013.
  
• Efficient Construction of Global Time in SoCs despite Arbitrary Faults
  Matthias Fuegger, Markus Hofstaetter, Christoph Lenzen, and Ulrich Schmid.
  16th Conference on Digital System Design (DSD), September 2013.
  
• Byzantine Self-Stabilizing Clock Distribution with HEX: Implementation, Simulation, Clock Multiplication
  Christoph Lenzen, Martin Perner, Martin Sigl, and Ulrich Schmid .
  6th Conference on Dependability (DEPEND), August 2013.
  
• HEX: Scaling Honeycombs is Easier than Scaling Clock Trees
  Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner, and Ulrich Schmid.
  25th Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2013.
  
• Efficient Distributed Source Detection with Limited Bandwidth
  Christoph Lenzen and David Peleg.
  32nd Symposium on Principles of Distributed Computing (PODC), July 2013.
  
• Early-Deciding Consensus is Expensive
  Danny Dolev and Christoph Lenzen.
  32nd Symposium on Principles of Distributed Computing (PODC), July 2013.
  
• Optimal Deterministic Routing and Sorting on the Congested Clique
  Christoph Lenzen.
  32nd Symposium on Principles of Distributed Computing (PODC), July 2013.
  
• Fast Routing Table Construction Using Small Messages
  Christoph Lenzen and Boaz Patt-Shamir.
  45th Symposium on the Theory of Computing (STOC), June 2013.
  arxiv
  
• Distributed Minimum Dominating Set Approximations in Restricted Families of Graphs
  Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.
  Distributed Computing, 26(2):119-137, April 2013.
  preprint
  
• "Tri, Tri again": Finding Triangles and Small Subgraphs in a Distributed Setting
  Danny Dolev, Christoph Lenzen, and Shir Peled.
  26th Symposium on Distributed Computing (DISC), October 2012.
  arxiv
  
• Distributed Algorithms for Wireless Networks
  Christoph Lenzen and Roger Wattenhofer. (Invited article)
  Philosophical Transactions of the Royal Society A, 370(1958), January 2012.
  preprint
  
• Coupling Molecular Dynamics and Continua with Weak Constraints
  Konstantin Fackeldey, Dorian Krause, Rolf Krause, and Christoph Lenzen.
  SIAM Journal on Multiscale Modeling and Simulation, 9(4), November 2011.
  preprint
  
• Fault-tolerant Algorithms for Tick-generation in Asynchronous Logic: Robust Pulse Generation
  Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
  13th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), October 2011.
  arxiv
  
• Tight Bounds for Parallel Randomized Load Balancing
  Christoph Lenzen and Roger Wattenhofer.
  43rd Symposium on Theory of Computing (STOC), June 2011.
  arxiv
  
• MIS on Trees
  Christoph Lenzen and Roger Wattenhofer.
  30th Symposium on Principles of Distributed Computing (PODC), June 2011.
  
• Synchronization and Symmetry Breaking in Distributed Systems
  Christoph Lenzen. (ETH medal for outstanding thesis)
  Diss. ETH No. 19459, Ph.D. thesis, ETH Zurich, January 2011.
  
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
  Christoph Lenzen and Roger Wattenhofer.
  24th Symposium on Distributed Computing (DISC), September 2010.
  
• Optimal Gradient Clock Synchronization in Dynamic Networks
  Fabian Kuhn, Christoph Lenzen, Thomas Locher, and Rotem Oshman. (Best Paper Session)
  29th Symposium on Principles of Distributed Computing (PODC), July 2010.
  technical report
  
• Brief Announcement: Exponential Speed-Up of Local Algorithms using Non-Local Communication
  Christoph Lenzen and Roger Wattenhofer.
  29th Symposium on Principles of Distributed Computing (PODC), July 2010.
  
• Clock Synchronization: Open Problems in Theory and Practice
  Christoph Lenzen, Thomas Locher, Philipp Sommer, and Roger Wattenhofer. (Invited paper)
  36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), January 2010.
  
• Tight Bounds for Clock Synchronization
  Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.
  Journal of the ACM, Volume 57, Number 2, January 2010.
  
• Local Algorithms: Self-Stabilization on Speed
  Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer. (Invited paper)
  11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2009.
  
• Optimal Clock Synchronization in Networks
  Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
  7th ACM Conference on Embedded Networked Sensor Systems (SenSys), November 2009.
  
• Tight Bounds for Clock Synchronization
  Christoph Lenzen, Thomas Locher, and Roger Wattenhofer. (Best Paper Award)
  28th ACM Symposium on Principles of Distributed Computing (PODC), August 2009.
  technical report
  
• Clock Synchronization with Bounded Global and Local Skew
  Christoph Lenzen, Thomas Locher, and Roger Wattenhofer.
  49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 2008.
  technical report
  
• Leveraging Linial's Locality Limit
  Christoph Lenzen and Roger Wattenhofer.
  22nd International Symposium on Distributed Computing (DISC), September 2008.
  
• What Can Be Approximated Locally? Case Study: Dominating Sets in Planar Graphs
  Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer.
  22nd Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2008.
  technical report