Credits: 5
Schedule: 07.01.2019 - 01.04.2019
Teaching Period (valid 01.08.2018-31.07.2020):
III-IV Spring (2018-2019, 2019-2020)
Learning Outcomes (valid 01.08.2018-31.07.2020):
Having completed this course, you will be familiar with an area in the foundations of cryptography on a level of familiarity that is required for engaging in research in that area. You will be able to use techniques from algorithm analysis, complexity theory and/or discrete mathematics to study the hardness of a class of average-case problems. The content of the course varies and so do the learning outcomes. In particular, the classes of average-case hard problems vary from semester to semester.
Content (valid 01.08.2018-31.07.2020):
The content varies each year and lies within the field of using discrete mathematics techniques for algorithm analysis. The Spring 2019 instance will cover algorithms for random constraint satisfaction problems as well as as algorithms for inverting Goldreich's one-way function. We will study solution spaces of the problems and see how those relate to algorithmic difficulty.
Assessment Methods and Criteria (valid 01.08.2018-31.07.2020):
Weekly exercises, course feedback (no exam)
Workload (valid 01.08.2018-31.07.2020):
Lectures 24h (12 2h-sessions), Teaching in small groups 24h (12 2h-sessions), weekly written exercises 36h, self-study ca. 40h
Study Material (valid 01.08.2018-31.07.2020):
Varies depending on the course content and will be announced later.
Course Homepage (valid 01.08.2018-31.07.2020):
https://mycourses.aalto.fi/course/search.php?search=MS-E1687
Prerequisites (valid 01.08.2018-31.07.2020):
Essential prerequisite skills are mathematical maturity and discrete probability theory. Highly recommended is a background in computability and complexity, especially basic complexity classes such as P and NP. It is further helpful to have a background in cryptography and/or algorithms.
Grading Scale (valid 01.08.2018-31.07.2020):
pass/fail