Homepage of Dennis Komm

Dennis Komm

Welcome to my personal homepage.

I am a lecturer at Juraj Hromkovič's Chair of Information Technology and Education at ETH Zürich.

Chair of Information Technology and Education
ETH Zürich
CAB F 13.1
Universitätstrasse 6
CH-8092 Zürich

Phone: +41 (0)44 632 82 23
Fax: +41 (0)44 632 13 90

E-Mail:

Intereststop

In theoretical computer science, my main topics of interest include

Also, I am interested in how to nicely communicate some of the basic ideas and concepts of computer science to (young) students.

Moreover, I enjoy hiking, snowboarding, traveling, LATEX, Linux, and Perl.

Curriculum Vitaetop

2014 – todayExternal lecturer at University of Zurich
2013 – todayLecturer at ETH Zürich
2012 – 2013Postdoctoral researcher at ETH Zürich
2010 – todayMember of Ausbildungs- und Beratungszentrum für Informatikunterricht, Switzerland
2009 – 2012Board member of Engineers without borders Switzerland
2008 – 2012PhD Student at ETH Zürich, Switzerland
2006Study of Information Technology at Queensland University of Technology, Australia
2002 – 2008Study of Computer Science at RWTH Aachen University, Germany

Since February 2013, I am voted the representative of the “akademischer Mittelbau” at the Conference on Education in Didactics at ETH.

In 2010 and 2014, I was an expert for Schweizer Jugend forscht.

In February 2010, I stayed at King's College, in June 2011, at RWTH Aachen University, and in March 2015 at Comenius University as a guest scientist.

Back in high school
Back in high school
Hiking
Hiking
Studies in Aachen
Studies in Aachen
Studies in Brisbane
Studies in Brisbane

I reviewed submissions to Algorithmic Operations Research, Fundamenta Informaticæ, Information Processing Letters, International Journal of Foundations of Computer Science, Journal of Scheduling, Parallel Processing Letters, RAIRO – Theoretical Informatics and Applications, Theoretical Computer Science, CIAA, COCOA, COCOON, CSR, DLT, ESA, ICALP, IFIP TCS, ISAAC, ISSEP, LATA, MEMICS, MFCS, SEA, SOFSEM, and WG.

In Chinese, my name is 丹尼斯; in Russian, it is ДЕНИС.

My Erdős number is at most 3 (D. Komm ↔ P. Rossmanith ↔ D. Kratsch ↔ P. Erdős).

My mathematical genealogy (created using Genealogy Grapher) can be found at the MGP.

Teachingtop

This autumn, I am giving a Python programming course with special focus on preparing for the Swiss olympiad in informatics.

In summer 2014, I gave a course on computational biology at Volkshochschule Zürich; lecture notes (in German): Summary 1, 2 (Handout), 3 (Handout), and 4.

Since 2010, together with colleagues from the ABZ, I gave some programming lessons for elementary school students at, e.g., Kantonsschule Solothurn, Primarschule Domat-Ems, Primarschule Saas im Prättgau, and Schweizerische Alpine Mittelschule Davos.

Courses at University of Zurich

Autumn 2014 – 2017Foundations of Computing II; download lecture notes

Courses at ETH

Spring 2016Entwurfsmethoden für zufallsgesteuerte Algorithmen
Spring 2015Algorithmik für schwere Probleme
Autumn 2015Einsatz von Informatikmitteln
Autumn 2014 – 2016Grundlagen der Informatik
Spring 2013 – 2017Approximations- und Online-Algorithmen; download lecture notes (in German)

Groups at ETH

Autumn 2013Grundlagen der Informatik
Autumn 2009 – 2017Theory of Computing
Spring 2012Informatik für Biologie und pharmazeutische Wissenschaften
Spring 2011Algorithmik für schwere Probleme
Spring 2009, 2010Entwurfsmethoden von zufallsgesteuerten Systemen

Supervised Theses

You can use a template to typeset your bachelor's or master thesis (example and resulting PDF).

Co-Refereed Theses

Publicationstop

You can query DBLP for an overview of my publications; alternatively, you can check my Google Scholar page.

Just let me know if you are interested in any of the full papers.

An introduction to online computation: determinism, randomization, adviceI have recently written a book on online computation, which you can now order at Amazon.

An introduction to online computation: determinism, randomization, advice.

From the cover: “This textbook explains online computation in different settings, with particular emphasis on randomization and advice complexity. These settings are analyzed for various online problems such as the paging problem, the k-server problem, job shop scheduling, the knapsack problem, the bit guessing problem, and problems on graphs. This book is appropriate for undergraduate and graduate students of computer science, assuming a basic knowledge in algorithmics and discrete mathematics. Also researchers will find this a valuable reference for the recent field of advice complexity.”

Contains 101 exercises with solutions. ISBN: 978-3-319-42747-8, hardcover, Springer-Verlag 2016, 349 pages.

Publications in Refereed Journals

  1. M. P. Bianchi, H.-J. Böckenhauer, T. Brülisauer, D. Komm, and B. Palano:
    Online minimum spanning tree with advice.
    International Journal of Foundations of Computer Science, 2017, accepted for publication.
  2. S. Dobrev, J. Edmonds, D. Komm, R. Královič, R. Královič, S. Krug, and T. Mömke:
    Improved analysis of the online set cover problem with advice.
    Theoretical Computer Science 689, 2017, pages 96–107.
  3. H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič, and T. Mömke:
    Online algorithms with advice: the tape model.
    Information and Computation 254, 2017, pages 59–83.
  4. H.-J. Böckenhauer, D. Komm, R. Královič, and R. Královič:
    On the advice complexity of the k-server problem.
    Journal of Computer and System Sciences 86, 2017, pages 159–170.
  5. H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, and A. Sprock:
    The string guessing problem as a method to prove lower bounds on the advice complexity.
    Theoretical Computer Science 554, 2014, pages 95–108.
  6. H.-J. Böckenhauer, D. Komm, R. Královič, and P. Rossmanith:
    The online knapsack problem: advice and randomization.
    Theoretical Computer Science 527, 2014, pages 61–72.
  7. D. Komm and R. Královič:
    Advice complexity and barely random algorithms.
    Theoretical Informatics and Applications (RAIRO ITA) 45(2), 2011, pages 249–267.
  8. D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královič, T. Mömke, S. Seibert, and A. Zych:
    Reoptimization of the shortest common superstring problem.
    Algorithmica 61(2), 2011, pages 227–251.
  9. H.-J. Böckenhauer and D. Komm:
    Reoptimization of the metric deadline TSP.
    Journal of Discrete Algorithms 8, 2010, pages 87–100.

Publications in Refereed Books and Proceedings

  1. E. Burjons, D. Komm, and M. Schöngens:
    The k-server problem with advice in dimensions and on the sphere.
    In Proc. of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2018), to appear.
  2. J. Hromkovič, T. Kohn, D. Komm, and G. Serafini:
    Combining the power of Python with the simplicity of Logo for a sustainable computer science education.
    In Proc. of the 9th International Conference on Informatics in Secondary Schools (ISSEP 2016), volume 9973 of Lecture Notes in Computer Science, Springer-Verlag 2016, pages 155–166.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  3. J. Clemente, J. Hromkovič, D. Komm, and Ch. Kudahl:
    Advice complexity of the online search problem.
    In Proc. of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), volume 9843 of Lecture Notes in Computer Science, Springer-Verlag 2016, pages 203–212.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  4. D. Komm, R. Královič, R. Královič, and Ch. Kudahl:
    Advice complexity of the online induced subgraph problem.
    In Proc. of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics, pages 59:1–59:13.
    PDF available online via drops.dagstuhl.de, (c) Schloss Dagstuhl—Leibniz-Zentrum für Informatik.
  5. S. Dobrev, J. Hromkovič, D. Komm, R. Královič, R. Královič, and T. Mömke:
    The complexity of paging against a probabilistic adversary.
    In Proc. of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), volume 9587 of Lecture Notes in Computer Science, Springer-Verlag 2016, pages 265–276.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  6. M. P. Bianchi, H.-J. Böckenhauer, T. Brülisauer, D. Komm, and B. Palano:
    Online minimum spanning tree with advice (Extended abstract).
    In Proc. of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), volume 9587 of Lecture Notes in Computer Science, Springer-Verlag 2016, pages 195–207.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  7. D. Komm, R. Královič, R. Královič, and J. Smula:
    Treasure hunt with advice.
    In Proc. of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015), volume 9439 of Lecture Notes in Computer Science, Springer-Verlag 2015, pages 328–341.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  8. H. Gebauer, D. Komm, R. Královič, R. Královič, and J. Smula:
    Disjoint path allocation with sublinear advice.
    In Proc. of the 21st International Conference on Computing and Combinatorics (COCOON 2015), volume 9198 of Lecture Notes in Computer Science, Springer-Verlag 2015, pages 417–429.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  9. D. Komm, R. Královič, R. Královič, and T. Mömke:
    Randomized online algorithms with high probability guarantees.
    In Proc. of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics, pages 470–481.
    PDF available online via drops.dagstuhl.de, (c) Schloss Dagstuhl—Leibniz-Zentrum für Informatik.
  10. H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, and A. Sprock:
    The string guessing problem as a method to prove lower bounds on the advice complexity (Extended abstract).
    In Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013), volume 7936 of Lecture Notes in Computer Science, Springer-Verlag 2013, pages 493–505.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  11. D. Komm, R. Královič, and T. Mömke:
    On the advice complexity of the set cover problem.
    In Proc. of the 7th International Computer Science Symposium in Russia (CSR 2012), volume 7353 of Lecture Notes in Computer Science, Springer-Verlag 2012, pages 241–252.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  12. H.-J. Böckenhauer, D. Komm, R. Královič, and P. Rossmanith:
    On the advice complexity of the knapsack problem.
    In Proc. of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), volume 7256 of Lecture Notes in Computer Science, Springer-Verlag 2012, pages 61–72.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  13. H.-J. Böckenhauer, D. Komm, R. Královič, and R. Královič:
    On the advice complexity of the k-server problem.
    In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), volume 6755 of Lecture Notes in Computer Science, Springer-Verlag 2011, pages 207–218.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  14. D. Komm and R. Královič:
    Advice complexity and barely random algorithms.
    In Proc. of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), volume 6543 of Lecture Notes in Computer Science, Springer-Verlag 2011, pages 332–343.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  15. L. Keller, D. Komm, G. Serafini, A. Sprock, and B. Steffen:
    Teaching public-key cryptography in school.
    In Proc. of the 4th International Conference on Informatics in Secondary Schools: Evolution and Perspectives (ISSEP 2010), volume 5941 of Lecture Notes in Computer Science, Springer-Verlag 2010, pages 112–123.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  16. H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič, and T. Mömke:
    On the advice complexity of online problems (Extended abstract).
    In Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), volume 5878 of Lecture Notes in Computer Science, Springer-Verlag 2009, pages 331–340.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  17. D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královič, T. Mömke, S. Seibert, and A. Zych:
    Reoptimization of the shortest common superstring problem (Extended abstract).
    In Proc. of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), volume 5577 of Lecture Notes in Computer Science, Springer-Verlag 2009, pages 78–91.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  18. H.-J. Böckenhauer and D. Komm:
    Reoptimization of the metric deadline TSP (Extended abstract).
    In Proc. of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), volume 5162 of Lecture Notes in Computer Science, Springer-Verlag 2008, pages 156–167.
    PDF available online via SpringerLink, (c) Springer-Verlag.

Invited Publications in Books and Proceedings

  1. J. Hromkovič, T. Kohn, D. Komm, and G. Serafini:
    Algorithmic thinking from the start.
    Bulletin of the EATCS 121, The Education Column, 2017.
    PDF available online at bulletin.eatcs.org/index.php/beatcs/issue/view/23, (c) European Association for Theoretical Computer Science.
  2. H.-J. Böckenhauer, J. Hromkovič, and D. Komm:
    A technique to obtain hardness results for randomized online algorithms.
    In Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, volume 8808 of Lecture Notes in Computer Science, Springer-Verlag 2014, pages 264–276.
    PDF available online via SpringerLink, (c) Springer-Verlag.
  3. H.-J. Böckenhauer, J. Hromkovič, D. Komm, R. Královič, and P. Rossmanith:
    On the power of randomness versus advice in online computation.
    In Languages Alive: Essays Dedicated to J├╝rgen Dassow on the Occasion of His 65th Birthday, volume 7300 of Lecture Notes in Computer Science, Springer-Verlag 2012, pages 30–43.
    PDF available online via SpringerLink, (c) Springer-Verlag.

Teaching Material

  1. D. Komm:
    An introduction to the theory of computing.
    Lecture Notes, University of Zurich, 2017.
    PDF available online.
  2. L. Fässler, M. Dahinden, D. Komm, and D. Sichau:
    Einführung in die Programmierung mit Python und Matlab.
    Begleitunterlagen zum Onlinekurs und zur Vorlesung, 2015.
    Order at Amazon.
  3. D. Komm:
    Eine Einführung in Online-Algorithmen.
    Lecture Notes, ETH Zürich, 2017.
    PDF available online.
  4. H.-J. Böckenhauer, D. Komm, and J. Hromkovič:
    Programmieren mit LOGO für Fortgeschrittene.
    Lecture Notes, ETH Zürich, 2015.
    PDF available online at www.abz.inf.ethz.ch (the basics can be found here).
  5. H.-J. Böckenhauer, D. Komm, and J. Hromkovič:
    Programmieren mit LOGO — Projekte.
    Lecture Notes, ETH Zürich, 2015.
    PDF available online at www.abz.inf.ethz.ch.

Technical Reports

  1. J. Clemente, J. Hromkovič, D. Komm, and Ch. Kudahl:
    Advice complexity of the online search problem.
    CoRR abs/1612.09299, 2016.
    PDF available online at arxiv.org/abs/1612.09299.
  2. D. Komm, R. Královič, R. Královič, and Ch. Kudahl:
    Advice complexity of the online induced subgraph problem.
    CoRR abs/1512.05996, 2015.
    PDF available online at arxiv.org/abs/1512.05996.
  3. H.-J. Böckenhauer, S. Geulen, D. Komm, and W. Unger:
    Constructing randomized online algorithms from algorithms with advice.
    Technical Report 48298, 2015.
    PDF available online at e-collection.library.ethz.ch/view/eth:48298.
  4. D. Komm, R. Královič, R. Královič, and T. Mömke:
    Randomized online computation with high probability guarantees.
    CoRR abs/1302.2805, 2013.
    PDF available online at arxiv.org/abs/1302.2805.
  5. H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, and A. Sprock:
    The string guessing problem as a method to prove lower bounds on the advice complexity.
    Electronic Colloquium on Computational Complexity, TR12-162, 2012.
    PDF available online at eccc.hpi-web.de/report/2012/162.
  6. H.-J. Böckenhauer, D. Komm, R. Královič, and P. Rossmanith:
    On the advice complexity of the knapsack problem.
    Technical Report 740, ETH Zürich, 2011.
    PDF available online at e-collection.library.ethz.ch.
  7. D. Komm, R. Královič, and T. Mömke:
    On the advice complexity of the set cover problem.
    Technical Report 738, ETH Zürich, 2011.
    PDF available online at e-collection.library.ethz.ch.
  8. H.-J. Böckenhauer, D. Komm, R. Královič, and R. Královič:
    On the advice complexity of the k-server problem.
    Technical Report 703, ETH Zürich, 2010.
    PDF available online at e-collection.library.ethz.ch.
  9. D. Komm and R. Královič:
    Advice complexity and barely random algorithms.
    Technical Report 684, ETH Zürich, 2010.
    PDF available online at e-collection.library.ethz.ch.
  10. H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič, and T. Mömke:
    Online algorithms with advice.
    Technical Report 614, ETH Zürich, 2009.
    PDF available online at e-collection.library.ethz.ch.

Other Publications

  1. D. Komm and T. Kohn:
    An introduction to running time analysis for an SOI workshop.
    Olympiads in Informatics 11:77–86, 2017.
    PDF available online at www.ioinformatics.org/oi/shtm/v11_2017_77_86.shtml.
  2. J. Hromkovič, T. Kohn, D. Komm, and G. Serafini:
    Examples of algorithmic thinking in programming education.
    Olympiads in Informatics 10:111–124, 2016.
    PDF available online at www.ioinformatics.org/oi/shtm/v10_2016_111_124.shtml.
  3. J. Hromkovič, L. Keller, D. Komm, G. Serafini, and B. Steffen:
    Entdeckendes Lernen am Beispiel fehlerkorrigierender Codes.
    Log-in 168:50–55, 2011.
  4. D. Komm:
    Teaching the concept of online algorithms.
    Olympiads in Informatics 5:58–71, 2011.
    PDF available online at www.ioinformatics.org/oi_content_v5.shtml.
  5. H. Bruderer and D. Komm:
    Programmieren und denkend Probleme lösen.
    Bildung Schweiz 11a:31 Sonderheft Computer und Internet, 2009.
    PDF available online at www.lch.ch/publikationen/bildung-schweiz.

Theses

  1. D. Komm:
    Advice and randomization in online computation.
    PhD Thesis, ETH Zürich, 2012. Supervisor: J. Hromkovič; Co-Referees: P. Widmayer, G. Schnitger. Defended on 21.12.2011.
    PDF available online at www.research-collection.ethz.ch/handle/20.500.11850/72815.
  2. D. Komm:
    Optimierung und Reoptimierung des metrischen Traveling-Salesman-Problems mit Deadlines.
    Diploma Thesis, RWTH Aachen University, 2008. Supervisor: P. Rossmanith.

Some Talks and Workshops

Photostop

Some visual impressions of the past years; these are snapshots.

Brisbane, Australia, 2006
Brisbane, Australia, 2006
Rohan, New Zealand, 2006
Rohan, New Zealand, 2006
Pitztal, Austria, 2008
Pitztal, Austria, 2008
Venice, Italy, 2009
Venice, Italy, 2009
Venice, Italy, 2009
Venice, Italy, 2009
Venice, Italy, 2009
Venice, Italy, 2009
Davos, Switzerland, 2009
Davos, Switzerland, 2009
Davos, Switzerland, 2009
Davos, Switzerland, 2009
Rottweil, Germany, 2010
Rottweil, Germany, 2010
Königsfeld, Germany, 2010
Königsfeld, Germany, 2010
Königsfeld, Germany, 2010
Königsfeld, Germany, 2010
Königsfeld, Germany, 2010
Königsfeld, Germany, 2010
Vienna, Austria, 2010
Vienna, Austria, 2010
Bratislava, Slovakia, 2010
Bratislava, Slovakia, 2010
Bratislava, Slovakia, 2010
Bratislava, Slovakia, 2010
Europapark Rust, Germany, 2010
Europapark Rust, Germany, 2010
Andermatt, Switzerland, 2010
Andermatt, Switzerland, 2010
Rome, Italy, 2010
Rome, Italy, 2010
Rome, Italy, 2010
Rome, Italy, 2010
Cologne, Germany, 2011
Cologne, Germany, 2011
Zermatt, Switzerland, 2011
Zermatt, Switzerland, 2011
Highlands, Scotland, 2011
Highlands, Scotland, 2011
Highlands, Scotland, 2011
Highlands, Scotland, 2011
Stockholm, Sweden, 2011
Stockholm, Sweden, 2011
High Fens, Belgium, 2011
High Fens, Belgium, 2011
Zürich, Switzerland, 2011
Zürich, Switzerland, 2011
Zürich, Switzerland, 2012
Zürich, Switzerland, 2012
Arequipa, Peru, 2012
Arequipa, Peru, 2012
Colca Canyon, Peru, 2012
Colca Canyon, Peru, 2012
Colca Canyon, Peru, 2012
Colca Canyon, Peru, 2012
Tuscany, Italy, 2012
Tuscany, Italy, 2012
Tuscany, Italy, 2012
Tuscany, Italy, 2012
St. Petersburg, Russia, 2012
St. Petersburg, Russia, 2012
Provence, France, 2012
Provence, France, 2012
Paris, France, 2012
Paris, France, 2012
California, USA, 2013
California, USA, 2013
California, USA, 2013
California, USA, 2013
Death Valley, USA, 2013
Death Valley, USA, 2013
Locarno, Switzerland, 2013
Locarno, Switzerland, 2013
Malta, 2013
Malta, 2013
Malta 2013
Malta, 2013
Mallorca, 2014
Mallorca, 2014
Copenhagen, Denmark, 2014
Copenhagen, Denmark, 2014
Lachen, Switzerland, 2014
Lachen, Switzerland, 2014
Rhône Glacier, Switzerland, 2014
Rhône Glacier, Switzerland, 2014
Dolomites, Italy, 2014
Dolomites, Italy, 2014
Valais, Switzerland, 2014
Valais, Switzerland, 2015
Granada, Spain, 2015
Granada, Spain, 2015
Córdoba, Spain, 2015
Córdoba, Spain, 2015
California, USA, 2015
California (Going going, back back...)
Nevada, USA, 2014
Nevada, USA, 2015
Zion National Park, USA, 2015
Zion National Park, USA, 2015
Lower Antelope Canyon, USA, 2015
Lower Antelope Canyon, USA, 2015
Chinese Wall, China, 2015
Chinese Wall, China, 2015
Pyrenees, Spain, 2015
Pyrenees, Spain, 2015
Whitehaven Beach, Australia, 2016
Whitehaven Beach, Australia, 2016
Piedmont, Italy, 2016
Piedmont, Italy, 2016
Bandera, USA, 2016
Bandera, USA, 2016
Helsinki, Finland, 2016
Helsinki, Finland, 2016
Gindelwald, Switzerland, 2017
Grindelwald, Switzerland, 2017