Christoph Lenzen
Research Homepage
Research Homepage
December 2023 - May 2025: StartUpSecure grant "Zeitsynchronisation für 5G und 6G Netzwerke: sicher, präzise, zuverlässig" for startup Timelords UG.
August 2023 - July 2024: ERC proof-of-concept grant "Gradient Clock Synchronization for Networks-on-Chip and Cellular Networks" aiming at commercialisation of results from the ERC starting grant.
July 2021 - present: faculty member at CISPA.
2021: ERC proof-of-concept grant "Fast Response Circuits for Voltage Droop Compensation" aiming at commercialisation of results from the ERC starting grant.
2017 - 2022: ERC starting grant project "A Theory of Reliable Hardware."
July 2014 - June 2021: Group Leader at MPI for Informatics.
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.
summer 2025: Theory on Consensus
summer 2023: Theory on Consensus
winter 2022/23: Clock Synchronization and Adversarial Fault Tolerance
summer 2022: How To Clock Your Computer
winter 2021/22: Metastability-containing Synchronization Circuits
summer 2021: Clock Synchronization and Adversarial Fault Tolerance
winter 2020/21: How To Clock Your Computer
winter 2020/21: Theory of Distributed Systems
winter 2019/20: Theory of Distributed Systems
summer 2019: Keeping Time in Distributed Systems
winter 2018/19: Theory of Distributed Systems
summer 2018: Keeping Time in Distributed Systems
winter 2017/18: Theory of Distributed Systems
winter 2016/17: Theory of Distributed Systems
winter 2015/16: Theory of Distributed Systems
winter 2014/15: Theory of Distributed Systems
Model-Agnostic Approximation of Constrained Forest Problems
Corinna Coupette, Alipasha Montaseri, and Christoph Lenzen.
Symposium on Distributed Computing (DISC), October 2025.
arxiv
Nearly Optimal Parallel Broadcast in the Plain Public Key Model
Ran Gelles, Christoph Lenzen, Julian Loss, and Sravya Yandamuri.
Symposium on Principles of Distributed Computing (PODC), June 2025.
ePrint
Clock Distribution with Gradient Trix
Shreyas Srinivas and Christoph Lenzen.
Symposium on Principles of Distributed Computing (PODC), June 2025.
arxiv
Small Hazard-Free Transducers
Johannes Bund, Christoph Lenzen, and Moti Medina.
Transactions on Computers, 2025.
arxiv
GRandLine: Adaptively Secure DKG and Randomness Beacon with (Log-)Quadratic Communication Complexity
Renas Bacho, Christoph Lenzen, Julian Loss, Simon Ochsenreither, and Dimitrios Papachristoudis.
Conference on Computer and Communications Security (CCS), 2024.
ePrint
Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
Christoph Lenzen and Sophie Wenning.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2024.
arxiv
Decentralized Low Stretch Trees via Low Diameter Graph Decompositions
Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen.
SIAM Journal on Computing, vol. 53(2), pp. 247–286, February 2024.
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis.
Distributed Computing, vol. 36(4), pp. 475–499, July 2023.
Robust Routing Made Easy: Reinforcing Networks Against Non-Benign Faults
Christoph Lenzen, Moti Medina, Mehrdad Saberi, and Stefan Schmid.
Transactions on Networking, vol. 32(1), pp. 283–297, 2023.
Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis.
Symposium on Distributed Computing (DISC), October 2022.
arxiv (full version)
G-SINC: Global Synchronization Infrastructure for Network Clocks
Marc Frei, Jonghoon Kwon, Seyedali Tabaeiaghdaei, Marc Wyss, Christoph Lenzen, and Adrian Perrig.
Symposium on Reliable Distributed Systems (SRDS), September 2022.
A Recursive Early-Stopping Phase King Protocol
Christoph Lenzen and Sahar Sheikholeslami.
Symposium on Principles of Distributed Computing (PODC), July 2022.
Optimal Clock Synchronization with Signatures
Christoph Lenzen and Julian Loss.
Symposium on Principles of Distributed Computing (PODC), July 2022.
On Specifications and Proofs of Timed Circuits
Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid.
Thomas Henzinger Festschrift - Conference celebrating his 60th birthday, 2022.
Small Hazard-Free Transducers
Johannes Bund, Christoph Lenzen, and Moti Medina.
Innovations in Theoretical Computer Science (ITCS), January 2022.
arxiv (full version)
Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Ben Wiederhake.
Transactions on Computer-Aided Design of Integrated Circuits and Systems, July 2021.
Approximate Minimum Directed Spanning Trees under Congestion
Christoph Lenzen and Hossein Vahidi.
28th Colloquium on Structural Information and Communication Complexity (SIROCCO), June 2021.
preprint
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen.
SIAM Journal on Computing, May 2021.
arxiv
A Breezing Proof of the KMW Bound
Corinna Coupette and Christoph Lenzen.
Symposium on Simplicity in Algorithms (SOSA), January 2021.
arxiv (full version)
Brief Announcement: TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware
Christoph Lenzen and Ben Wiederhake.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2020.
arxiv (full version)
PALS: Plesiochronous and Locally Synchronous Systems
Johannes Bund, Matthias Fuegger, Christoph Lenzen, Moti Medina, and Will Rosenbaum.
26th Symposium on Asynchronous Circuits and Systems (ASYNC), May 2020.
arxiv (full version)
Synchronizer-free Digital Link Controller
Johannes Bund, Matthias Fuegger, Christoph Lenzen, and Moti Medina.
Transactions on Circuits and Systems I, May 2020.
Fooling views: a new lower bound technique for distributed computations under congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Christoph Lenzen.
Distributed Computing, April 2020.
arxiv
Low Diameter Graph Decompositions by Approximate Distance Computation
Ruben Becker, Yuval Emek, and Christoph Lenzen.
11th Conference on Innovations in Theoretical Computer Science (ITCS), January 2020.
preprint
Distributed Algorithms for Low Stretch Spanning Trees
Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen.
33rd Symposium on Distributed Computing (DISC), October 2019.
preprint
Optimal Metastability-Containing Sorting via Parallel Prefix Computation
Johannes Bund, Christoph Lenzen, and Moti Medina.
Transactions on Computers, October 2019.
preprint (full version with proofs)
Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen and Joel Rybicki.
Journal of the ACM, August 2019.
preprint
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah.
Journal of the ACM, August 2019.
preprint
Fault Tolerant Gradient Clock Synchronization
Johannes Bund, Christoph Lenzen, and Will Rosenbaum.
38th Symposium on Principles of Distributed Computing (PODC), July 2019.
arxiv
Locality of not-so-weak coloring
Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela.
26th Colloquium on Structural Information and Communication Complexity (SIROCCO), July 2019.
arxiv
Parallel Balanced Allocations: The Heavily Loaded Case
Christoph Lenzen, Merav Parter, and Eylon Yogev.
31st Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2019.
preprint
Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir.
SIAM Journal on Computing, November 2018.
Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen and Joel Rybicki.
Distributed Computing, September 2018.
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs and Christoph Lenzen.
Journal of the ACM, August 2018.
A Local Algorithm for the Sparse Spanning Graph Problem
Christoph Lenzen and Reut Levi.
45th Colloquium on Automata, Languages, and Programming (ICALP), July 2018.
arxiv
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah.
50th Symposium on the Theory of Computing (STOC), June 2018.
arxiv
Fast All-Digital Clock Frequency Adaptation Circuit for Voltage Droop Tolerance
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Ben Wiederhake.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2018.
preprint
Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, and Moti Medina.
Design, Automation and Test in Europe (DATE), March 2018.
arxiv
Metastability-Containing Circuits
Stephan Friedrichs, Matthias Fuegger, and Christoph Lenzen.
IEEE Transactions on Computers, March 2018.
Distributed Distance Computation and Routing with Small Messages
Christoph Lenzen, Boaz Patt-Shamir, and David Peleg.
Distributed Computing, February 2018.
Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Pankaj Khanchandani and Christoph Lenzen.
Theory of Computing Systems, January 2018.
preprint
Robust Routing Made Easy
Christoph Lenzen and Moti Medina.
19th Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2017.
arxiv
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen.
31st Symposium on Distributed Computing (DISC), October 2017.
arxiv
Self-stabilising Byzantine Clock Synchronisation is Almost as Easy as Consensus
Christoph Lenzen and Joel Rybicki.
31st Symposium on Distributed Computing (DISC), October 2017.
arxiv
Efficient Counting with Optimal Resilience
Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
SIAM Journal on Computing, 46(4):1473-1500, August 2017.
preprint
Searching without Communicating: Tradeoffs Between Performance and Selection Complexity
Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva.
Distributed Computing, 30(3):169-191, June 2017.
preprint
Metastability-Aware Memory-Efficient Time-to-Digital Converters
Matthias Fuegger, Attila Kinali, Christoph Lenzen, and Thomas Polzer.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017.
Metastability Tolerant Computing
Ghaith Tarawneh, Matthias Fuegger, and Christoph Lenzen.
Symposium on Asynchronous Circuits and Systems (ASYNC), May 2017.
Near-Optimal Metastability-Containing Sorting Networks
Johannes Bund, Christoph Lenzen, and Moti Medina.
Design, Automation and Test in Europe (DATE), March 2017.
Self-stabilizing Byzantine Clock Synchronization with Optimal Precision
Pankaj Khanchandani and Christoph Lenzen.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2016.
arxiv
Near-Optimal Self-Stabilising Counting and Firing Squads
Christoph Lenzen and Joel Rybicki.
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), November 2016.
arxiv
Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.
Distributed Computing, March 2016.
preprint
HEX: Scaling Honeycombs is Easier than Scaling Clock Trees
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner, and Ulrich Schmid.
Journal of Computer and System Sciences, 82(5):929-956, August 2016.
preprint
Fault-tolerant Clock Synchronization with High Precision
Attila Kinali, Florian Huemer, and Christoph Lenzen.
Symposium on VLSI (ISVLSI), July 2016.
preprint
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Stephan Friedrichs and Christoph Lenzen.
25th Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2016.
arxiv
Efficient Metastability-Containing Gray Code 2-Sort
Christoph Lenzen and Moti Medina.
22nd Symposium on Asynchronous Circuits and Systems (ASYNC), May 2016.
preprint
Tight Bounds for Parallel Randomized Load Balancing
Christoph Lenzen and Roger Wattenhofer.
Distributed Computing, 29(2):127-142, April 2016.
preprint
Synchronous Counting and Computational Algorithm Design
Danny Dolev, Keijo Heljanko, Matti Järvisalo, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, Jukka Suomela, and Siert Wieringa.
Journal of Computer and System Sciences, 82(2):310-332, March 2016.
preprint
Efficient counting with optimal resilience
Christoph Lenzen and Joel Rybicki.
29th Symposium on Distributed Computing (DISC), October 2015.
arxiv
Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
Fast Partial Distance Estimation and Applications
Christoph Lenzen and Boaz Patt-Shamir.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki, and Jukka Suomela.
34th Symposium on Principles of Distributed Computing (PODC), July 2015.
preprint | arxiv
Fault-tolerant Distributed Systems in Hardware
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Ulrich Schmid, and Andreas Steininger. (Invited article)
EATCS Bulletin 116, June 2015.
PulseSync: An Efficient and Scalable Clock Synchronization Protocol
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer.
Transactions on Networking, 23(3):717-727, June 2015.
preprint
The 1-2-3 Toolkit for Building your own Balls-into-Bins Algorithm
Pierre Bertrand and Christoph Lenzen.
Meeting on Algorithm Engineering and Experiments (ALENEX), January 2015.
preprint | sources
Near-Optimal Distributed Tree Embedding
Mohsen Ghaffari and Christoph Lenzen.
28th Symposium on Distributed Computing (DISC), October 2014.
preprint
Brief Announcement: The 1-2-3 Toolkit for Building your own Balls-into-Bins Algorithm
Pierre Bertrand and Christoph Lenzen.
28th Symposium on Distributed Computing (DISC), October 2014.
preprint | sources
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, 61(5):860-900, August 2014.
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.
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):30, January 2014.
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 Sensor 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