Theoretical Computer Science Meets other Disciplines

Description of this Student Seminar (252-4303-00L)

Students present papers in Theoretical Computer Science which have also some "interdisciplinary flavor". Methods in classical theory of computing are used to better understand some fundamental questions in other fields (biology, social science, economics, etc.). The talks give a first outlook of these type of results which typically provide rigorous analysis of algorithms ("prove theorems").

Objectives: learn how to understand and present the key ideas and mathematical concepts in theory papers; Develop a critical attitude to evaluate the importance of a theoretical result and its practical relevance.

See also the course page in the ETH course catalog



Tame and Place: Thursdays, 10:00-12:00, virtual on zoom (see below for details).

Paper assignment: Papers will be assigned in a fair way using the random serial dictatorship algorithm: At the kickoff meeting we will pick a random order of students and, following this order, each student can choose his/her favorite paper among those that are still available. In order to make a good choice, it is fundamental that you look carefully into the available papers (listed below) before the kickoff meeting. It is well possible that your top choices will be taken when your turn to choose arrives, so it is in your best interest to have in mind several alternatives. In general, the length of the paper is not the main criteria to follow: in your presentation you do not have to talk about everything, but extract the most interesting/relevant parts. It is more important that you find the material interesting for you and you feel comfortable with the methodology/content (try to go beyond the introduction, and maybe look at some technical parts).

Demo talks (4 Mar): The instructor will give a "bad" talk followed by a (hopefully) better talk on the same topic.

Online talks on zoom and communications using piazza:

List of papers:

  1. The Small-World Phenomenon: An Algorithmic Perspective.
  2. A Note on the Computational Hardness of Evolutionary Stable Stategies.
  3. The ANTS Problem
  4. A Biological Solution to a Fundamental Distributed Computing Problem
  5. Sequential Defaulting in Finantial Networks
  6. The fashion game: Network extension of Matching Pennies
  7. Explainable k-Means and k-Medians Clusterings
  8. On the Elusiveness of Clusters
  9. A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem Mass Spectrometry
  10. Optimizing the Diamond Lane: A More Tractable Carpool Problem and Algorithms
  11. Card-Based Zero-Knowledge Proof for Sudoku
  12. The Othello game on an n x n board is PSPACE-complete
  13. Algorithms, games, and evolution
  14. Distributed Community Detection via Metastability of the 2-Choices Dynamics
  15. Distributed Computing on Core-Periphery Networks: Axiom-Based Design
  16. Fault-Tolerant ANTS
  17. Cooperating in Video Games? Impossible!Undecidability of Team Multiplayer Games
  18. Pooling or Sampling: Collective Dynamics
...more will be added if more students join

Final schedule:

(students who want, can share their slides after their presentation)
Day Presentation/Paper Speaker/Student Slides from Speaker
Julien Wolfensberger
Lukas Hasler
Presentation 1 (PPTX)
Presentation 2 (PDF)
Nicolas Kopp
Silas Gyger
Presentation 1 (PPTX)
Presentation 2 (PDF)
Alexander Schaller
Dominik Lehmann
Presentation 1 (PPTX)
Presentation 2 (PPTX)
Damian Cordes
Lukas Friedlos

Presentation 2 (PDF)
(no talk)
Yves Kempter

Presentation 2 (PPTX)
Ferdinand Nussbaum
Niels Saurer

Presentation 2 (PPTX)
Tobia Ochsner
Minh Khoi Trieu
Presentation 1 (PDF)
Presentation 2 (PDF)