Selected Topics of Theoretical Computer Science and Cryptography
The seminar “Selected Topics of Theoretical Computer Science and Cryptography” addresses current topics from the fields of complexity theory, algorithms and cryptography. It takes place in each semester, optionally in German or English.
Prerequisites for participation are the following Bachelor courses from the University of Mannheim or equivalent courses from other universities: Formal Foundations of Computer Science, Practical Computer Science I and II, Algorithms and Data Structures and Theoretical Computer Science or Cryptography I, respectively. Exceptionally, the prerequisite of the courses Theoretical Computer Science or Cryptography I can be disregarded. In this case, necessary prior knowledge of these areas will be imparted during the course of the seminar.
The topic description as well as organizational information about registration and execution of the seminar of the respective semester will be published on the website of the working group before the start of the semester.
The topic for the fall semester 2023 is “Game Complexity”. This seminar is intended for bachelor students. If you are interested in participating in this seminar, please register via Portal2.
Fall 2023 (Bachelor): Complexity Theoretical Classification of Games
Enthusiasm for games with two or more participants has been an integral part of human social life for many centuries. Generally, everyone knows games that are simple (or “boring”) in the sense that there are few different game sequences only and accordingly little room for creative and unexpected game ideas. In contrast to this, there are complex (or “demanding” or “interesting”) games, such as chess or go, for whose successful completion one can go to the limit of human intelligence and creativity.
We will deal with methods for formally determining whether a game is “boring” or “interesting” by the means of its set of rules. As a basis for this, we consider the problem of finding a winning strategy from a given game situation. To start with, this problem is to be formally described as a computational problem. In a further step, we then concentrate on methods to determine the complexity of this problem with regard to the schema of best-known complexity classes P, NP, PSPACE, etc. Besides elementary studies of computer science, preferable prerequisite for this seminar is the course Theoretical Computer Science. However, if required, the acquisition of basic complexity theoretical knowledge will be guided throughout the course of the seminar.
A meeting with the assignment of the topics will be held at the end of September.
Topic Selection
- PSPACE (Wikipedia)
- Sudoku (NP-complete, Paper)
- Candy Crush (NP-Hard, Paper)
- Minesweeper (CoNP-Complete, Paper1, Paper2)
- Othello (PSPACE-complete, Paper)
- Hex (PSPACE-complete, Paper1, Paper2)
- Super Mario Bros. (PSPACE-complete, Paper)
- Lemmings (PSPACE-complete, Paper)
- Go (PSPACE-complete, Paper)
- Trick-Taking Card Games (PSPACE-complete, Paper)
- Jigsaw puzzles (P, Paper)
Spring 2022 (Master): Homomorphic Encryption
In this seminar we will look at homomorphic encryption schemes. We will look at partiall homomorphic encryption as well as fully homomorphic encryption schemes.
The prerequisite for this seminar is the course Lineare Algebra I. For some topics it may be beneficial to have attended Cryptographie, Formal Foundations of Computer Science or advanced mathematic curses as Algebra.
As an comprehensive introduction into the topic, I can recommend this talk by Graig Gentry:
https://www.youtube.com/watch?v=487AjvFW1lkIf you are interested in participating in this seminar, please register at Portal2 until 14 February 2022.
Topic Selection:
The topics will be selected by mutual agreement.
Fall 2021 (Bachelor): Quantum Computing
In this seminar we will look at how a quantum computer operates. We will look at the computation model as well as algorithms and compare the algorithms' running time to that of a classical computer.
The prerequisite for this seminar is the course Lineare Algebra I. For some topics it may be beneficial to have attended Algorithmen und Datenstrukturen, Kryptografie I or Theoretische Informatik.
If you are interested in participating in this seminar, please take a look at the book by Yanofsky and Mannucci mentioned below. It will serve as the main source of information for the seminar.
As an introduction into the topic, I can recommend this talk by Microsoft Research:
https://www.youtube.com/watch?v=F_Riqjdh2oMThe seminar is intended to take place in German, though you may use English for your talk. If you are interested in participating in this seminar, please write an email to Alexander Moch. The registration deadline is 27 September 2021.
Literature:
Quantum Computing for Computer Scientists (2008)
by Noson S. Yanofsky and Mirco A. Mannucci.eBook available in the university's library:
https://primo.bib.uni-mannheim.de/permalink/f/19ojnqi/MAN_CUPCR9780511813887Topic Selection:
The topics will be based on the chapters of the book by Yanofsky and Mannucci.
Registration:
Please register by 27 September 2021 via email to Alexander Moch.
The seminar is meant for up to 10 participants. If the number of registrations exceeds 10, the participants will be selected based on their previous grades.
If you are not enrolled in the Business Informatics Bachelor's course please contact the examination board prior to registering for this course.
Spring 2021 (Master): Advanced Algorithms for Flow and Matching Problems
Flow- and Matching Problems occur in many real-life applications and the search for efficient algorithms for these types of problems represent a central topic in Combinatorial Optimization. In the Algorithmics course we discussed already basic Flow- and Matching algorithms like the Ford-Fulkerson method and the Edmonds Karp algorithm for the Maximum Flow Problem and MaxFlow-based algorithms for the Maximum Matching Problem for undirected bipartite graphs.
In this seminar we go some steps further and will deal with some more advanced algorithmic approaches leading to more efficient algorithms for more general types of Flow- and Matching problems. In this context, the modelling of Flow- and Matching problems as special instances of primal and dual linear programming will play an important role.
Literature: “Combinatorial Optimization” by William J. Cook, William H. Cunningham, William R. Pulleyblanc, Alexander Schrijver, John Wiley and Sons 1998, Chapters 1–5Topic Selection
- Push-Relabel Maximum Flow Algorithms
- Algorithms for Multicommodity Flows
- Primal- and Dual Minimum Cost Flow Algorithms
- Maximum Matching for general undirected graphs
- Minimum Weight Perfect Matching for bipartite weighted undirected graphs
- Minimum Weight Perfect Matching for general weighted undirected graphs
- ...
Fall 2020 (Bachelor): Quantum Computing
In this seminar we will look at how a quantum computer operates. We will look at the computation model as well as algorithms and compare the algorithms' running time to that of a classical computer.
The prerequisite for this seminar is the course Lineare Algebra I. For some topics it may be beneficial to have attended Algorithmen und Datenstrukturen, Kryptografie I or Theoretische Informatik.
If you are interested in participating in this seminar, please take a look at the book by Yanofsky and Mannucci mentioned below. It will serve as the main source of information for the seminar.
As an introduction into the topic, I can recommend this talk by Microsoft Research:
https://www.youtube.com/watch?v=F_Riqjdh2oMThe seminar is intended to take place in German, though you may use English for your talk. If you are interested in participating in this seminar, please write an email to Alexander Moch. The registration deadline is 5 October 2020.
Literature:
Quantum Computing for Computer Scientists (2008)
by Noson S. Yanofsky and Mirco A. Mannucci.eBook available in the university's library:
https://primo.bib.uni-mannheim.de/permalink/f/19ojnqi/MAN_CUPCR9780511813887Topic Selection:
The topics will be based on the chapters of the book by Yanofsky and Mannucci.
Registration:
Please register by 5 October 2020 via email to Alexander Moch.
The seminar is meant for up to 10 participants. If the number of registrations exceeds 10, the participants will be selected based on their previous grades.
Spring 2020 (Master): Advanced Algorithms for Flow and Matching Problems
Flow- and Matching Problems occur in many real-life applications and the search for efficient algorithms for these types of problems represent a central topic in Combinatorial Optimization. In the Algorithmics course we discussed already basic Flow- and Matching algorithms like the Ford-Fulkerson method and the Edmonds Karp algorithm for the Maximum Flow Problem and MaxFlow-based algorithms for the Maximum Matching Problem for undirected bipartite graphs.
In this seminar we go some steps further and will deal with some more advanced algorithmic approaches leading to more efficient algorithms for more general types of Flow- and Matching problems. In this context, the modelling of Flow- and Matching problems as special instances of primal and dual linear programming will play an important role.
Literature: “Combinatorial Optimization” by William J. Cook, William H. Cunningham, William R. Pulleyblanc, Alexander Schrijver, John Wiley and Sons 1998, Chapters 1–5Topic Selection
- Push-Relabel Maximum Flow Algorithms
- Algorithms for Multicommodity Flows
- Primal- and Dual Minimum Cost Flow Algorithms
- Maximum Matching for general undirected graphs
- Minimum Weight Perfect Matching for bipartite weighted undirected graphs
- Minimum Weight Perfect Matching for general weighted undirected graphs
- ...
Fall 2019 (Bachelor): Complexity Theoretical Classification of Games
Enthusiasm for games with two or more participants has been an integral part of human social life for many centuries. Generally, everyone knows games that are simple (or “boring”) in the sense that there are few different game sequences only and accordingly little room for creative and unexpected game ideas. In contrast to this, there are complex (or “demanding” or “interesting”) games, such as chess or go, for whose successful completion one can go to the limit of human intelligence and creativity.
We will deal with methods for formally determining whether a game is “boring” or “interesting” by the means of its set of rules. As a basis for this, we consider the problem of finding a winning strategy from a given game situation. To start with, this problem is to be formally described as a computational problem. In a further step, we then concentrate on methods to determine the complexity of this problem with regard to the schema of best-known complexity classes P, NP, PSPACE, etc. Besides elementary studies of computer science, preferable prerequisite for this seminar is the course Theoretical Computer Science. However, if required, the acquisition of basic complexity theoretical knowledge will be guided throughout the course of the seminar.
Registration via e-mail to Alexander Moch until 2 September 2019. Further information will then be provided by e-mail.
Topic Selection
- PSPACE (Wikipedia)
- Sudoku (NP-complete, Paper)
- Bejeweled (NP-Hard, Paper)
- Candy Crush (NP-Hard, Paper)
- Minesweeper (CoNP-Complete, Paper1, Paper2)
- Othello (PSPACE-complete, Paper)
- Hex (PSPACE-complete, Paper1, Paper2)
- Super Mario Bros. (PSPACE-complete, Paper)
- Lemmings (PSPACE-complete, Paper)
- Go (PSPACE-complete, Paper)