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, and is generally appropriate for both Bachelor's and Master's students.

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/winter semester 2019/2020 is „Complexity Theoretical Classification of Games“.

    • HWS2019/20: 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 September 2nd, 2019. Further information will then be provided by e-mail.

      Topic Selection