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

Instructor

• Paolo Penna

Organization

• Kickoff meeting (Feb 25): During this meeting papers will be assigned to you (your partecipation to the kickoff meeting is compulsory).
• Actual presentations (Mar 25 - Jun 3, tentative): The seminar is split into several weeks, every week we will have 2-3 presentations (see below for tentative schedule).
• Grading, minimal requirements: Your final grade will take into account the quality of the presentation (mainly) and also your active presence to the seminar; It is mandatory to attend at least five sessions/days (details will be discussed at the kickoff meeting and published shortly after).

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.

• Slides from the demo talks (here and here)
• Video of both demo talks (here)
• Slides of kickoff meeting (here)

Online talks on zoom and communications using piazza:

• Piazza (link here): We use piazza to improve communications and exchange of information in addition to emails. Please click on the link to sign up for this particular course, follow the discussion, get instructions on the use of zoom, and stay up to date.
• Zoom (online talks/classroom): We use zoom for giving presentations online. This allows all of us to participate actively as planned. The specific link for the "online classroom" in zoom will be communicated by the instructor on Piazza. To get familiar with the zoom system click here.

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
1 (25.03)	The Small-World Phenomenon: An Algorithmic Perspective A Note on the Computational Hardness of Evolutionary Stable Stategies	Julien Wolfensberger Lukas Hasler	Presentation 1 (PPTX) Presentation 2 (PDF)
2 (01.04)	The ANTS Problem A Biological Solution to a Fundamental Distributed Computing Problem	Nicolas Kopp Silas Gyger	Presentation 1 (PPTX) Presentation 2 (PDF)
3 (15.04)	Sequential Defaulting in Finantial Networks The fashion game: Network extension of Matching Pennies	Alexander Schaller Dominik Lehmann	Presentation 1 (PPTX) Presentation 2 (PPTX)
4 (22.04)	Explainable k-Means and k-Medians Clusterings On the Elusiveness of Clusters	Damian Cordes Lukas Friedlos	Presentation 2 (PDF)
5 (29.04)	Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games Optimizing the Diamond Lane: A More Tractable Carpool Problem and Algorithms	(no talk) Yves Kempter	Presentation 2 (PPTX)
6 (06.05)	Card-Based Zero-Knowledge Proof for Sudoku The Othello game on an n x n board is PSPACE-complete	Ferdinand Nussbaum Niels Saurer	Presentation 2 (PPTX)
7 (20.05)	Algorithms, games, and evolution Distributed Computing on Core-Periphery Networks: Axiom-Based Design	Tobia Ochsner Minh Khoi Trieu	Presentation 1 (PDF) Presentation 2 (PDF)