Tuomo Lempiäinen

D.Sc. (Tech.)

I am a recent graduate from Aalto University, Finland. I conducted my doctoral studies in the Distributed Algorithms group at the Department of Computer Science.

My research interests lie in the theory of computing, discrete mathematics and mathematical logic. In my doctoral research, I focused on the foundations of distributed computing.

I obtained my B.Sc. and M.Sc. degrees in mathematics, with a minor in computer science, from the University of Helsinki in 2013 and 2014, respectively. Previously I have worked in the New Paradigms in Computing group at the University of Helsinki and in the Natural Computation group at Aalto University.

Contact

tuomolempiainen.net

Links

Google Scholar · DBLP · LinkedIn

News

2019

• April 25: My dissertation was accepted and I obtained the degree of Doctor of Science (Technology).
• April 4: I am defending my doctoral dissertation at the Aalto University School of Science.

2018

• August 20–24: We are organising ALGO 2018 in Helsinki.
• February 9: New Classes of Distributed Time Complexity was accepted to STOC 2018.
• January–April: I am a teaching assistant on the course CS-E4530 Computational Complexity Theory.

2017

• December 20: I gave a talk at OPODIS 2017.
• November 22: I received the Nokia Scholarship.
• November 7: New manuscript: New Classes of Distributed Time Complexity.
• November 1: Constant Space and Non-Constant Time in Distributed Computing was accepted to OPODIS 2017.
• August 7–20: I am participating in NLS 2017 and LC 2017.
• July 16–22: I am participating in S3CS 2017.
• May 11: New manuscript: Constant Space and Non-Constant Time in Distributed Computing.

Publications

Refereed journal papers

• Weak models of distributed computing, with connections to modal logic.
  Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela and Jonni Virtema.
  Distributed Computing, volume 28, issue 1, pages 31–53, February 2015.
  Publisher's version · Authors' version · arXiv
• Search methods for tile sets in patterned DNA self-assembly.
  Mika Göös, Tuomo Lempiäinen, Eugen Czeizler and Pekka Orponen.
  Journal of Computer and System Sciences, volume 80, issue 1, pages 297–319, February 2014.
  Publisher's version · Authors' version · arXiv

Refereed conference papers

• New classes of distributed time complexity.
  Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti and Jukka Suomela.
  Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC, Los Angeles, CA, USA, June 2018), pages 1307–1318. ACM, 2018.
  Publisher's version · arXiv
• Constant space and non-constant time in distributed computing.
  Tuomo Lempiäinen and Jukka Suomela.
  Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS, Lisbon, Portugal, December 2017), volume 95 of LIPIcs, pages 30:1–30:16. Schloss Dagstuhl – Leibniz Center for Informatics, 2018.
  Publisher's version (open access!) · arXiv
• LCL problems on grids.
  Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R. J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela and Przemysław Uznański.
  Proceedings of the 36th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC, Washington, DC, USA, July 2017), pages 101–110. ACM, 2017.
  Publisher's version · arXiv
• Ability to count messages is worth Θ(Δ) rounds in distributed computing.
  Tuomo Lempiäinen.
  Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS, New York, NY, USA, July 2016), pages 357–366. ACM, 2016.
  Publisher's version · Authors' version · arXiv
• A lower bound for the distributed Lovász local lemma.
  Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela and Jara Uitto.
  Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC, Cambridge, MA, USA, June 2016), pages 479–488. ACM, 2016.
  Publisher's version · Authors' version · arXiv
• Weak models of distributed computing, with connections to modal logic.
  Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela and Jonni Virtema.
  Proceedings of the 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC, Funchal, Madeira, Portugal, July 2012), pages 185–194. ACM, 2012.
  Publisher's version · Authors' version · Journal version
• Synthesizing small and reliable tile sets for patterned DNA self-assembly.
  Tuomo Lempiäinen, Eugen Czeizler and Pekka Orponen.
  Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA, Pasadena, CA, USA, September 2011), volume 6937 of LNCS, pages 145–159. Springer, 2011.
  Publisher's version · Authors' version · Journal version

Other work presented at conferences and workshops

• New Classes of Distributed Time Complexity.
  Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti and Jukka Suomela.
  3rd Highlights of Algorithms (HALG, Amsterdam, the Netherlands, June 2018).
  Poster
• Nano Architectures for Carbon Nanotube Circuits: Design, Analysis, and Experimental Attempts.
  Eugen Czeizler, Tuomo Lempiäinen and Pekka Orponen.
  Workshop on Language Theory in Biocomputing (Turku, Finland, June 2011).
  Extended abstract
• Synthesizing Small and Reliable Tile Sets for Patterned DNA Self-Assembly.
  Tuomo Lempiäinen, Eugen Czeizler and Pekka Orponen.
  Workshop on Statistical Mechanics and Computation of DNA Self-Assembly (Mariehamn, Finland, May 2011).
  Poster
• A Design Framework for Carbon Nanotube Circuits Affixed on DNA Origami Tiles.
  Eugen Czeizler, Tuomo Lempiäinen and Pekka Orponen.
  Proceedings of the 8th Annual Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO, Snowbird, UT, USA, April 2011), pages 186–187.
  Extended abstract · Poster

Note that authors are listed in alphabetical order in the theoretical computer science papers.

Theses

• Logic and Complexity in Distributed Computing.
  Doctoral dissertation. Aalto University, Department of Computer Science, March 2019.
  
• The PATS Problem: Search Methods and Reliability.
  Minor subject thesis. University of Helsinki, Department of Computer Science, May 2015.
  
• A Classification of Weak Models of Distributed Computing.
  Master's thesis. University of Helsinki, Department of Mathematics and Statistics, November 2014.
  
• Bisimulaatio modaalilogiikassa.
  Bachelor's thesis. University of Helsinki, Department of Mathematics and Statistics, March 2013.
  

Talks

• Time and Space in Distributed Computing.
  17th May 2019. The Spring Meeting of Logicians in Tampere, Tampere University, Finland.
  
• Constant Space and Non-Constant Time in Distributed Computing.
  20th December 2017. The 21st International Conference on Principles of Distributed Systems (OPODIS), Lisbon, Portugal.
  
• Bisimulation and Modal Logic in Distributed Computing.
  8th December 2016. Computational Logic Day 2016, Aalto University, Finland.
  
• On the Existence of Constant-Space Non-constant-Time Distributed Algorithms.
  1st December 2016. Helsinki Algorithms Seminar, Aalto University, Finland.
  
• Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing.
  7th July 2016. The 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York, NY, USA.
  
• A Lower Bound for the Distributed Lovász Local Lemma.
  3rd December 2015. Helsinki Algorithms Seminar, University of Helsinki, Finland.
  
• A Lower Bound for the Distributed Lovász Local Lemma.
  25th November 2015. Graduiertenseminar "Theorie der künstlichen Intelligenz", University of Bremen, Germany.
  
• A Tight Lower Bound for Simulating Multiset Model by Set Model in Distributed Computing.
  20th February 2015. Finite Model Theory Seminar, University of Helsinki, Finland.
  
• The Value of Incoming Message Multiplicities in Distributed Computing.
  10th December 2014. Logic Seminar, University of Helsinki, Finland.
  

Teaching

• Computational Complexity Theory.
  Teaching assistant. Aalto University, spring 2018.
  
• Programming Parallel Computers.
  Teaching assistant. Aalto University, spring 2017.
  
• Computational Complexity Theory.
  Teaching assistant. Aalto University, spring 2017.
  
• Computational Complexity Theory.
  Teaching assistant. Aalto University, spring 2016.
  
• Programming Parallel Computers.
  Teaching assistant. Aalto University, spring 2015.