30516 - THEORETICAL COMPUTER SCIENCE

Strongly recommended: - Differential calculus; - Elementary graph theory; - Probability theory; - Elementary discrete mathematics; - Basic programming skills.

The aim of the course is to provide students with the mathematical tools that are the basis of the theory of algorithms, along with the mathematical methods used in modern computer science applications, such as cryptography. The rigorous approach enables the students to conjugate mathematical and algorithmic thinking. The chosen topics serve both as examples of powerful theoretical results (as well as the mathematical techniques employed to obtain them) and as key problems in Data Science which is encountered in the remainder of the education program.

• Algorithm Design: Graph algorithms, parallel and distributed algorithms, algorithmic game theory.
• Computational Complexity: Circuit lower bounds, communication complexity, hardness of approximation.
• Randomness in Computation: Randomized algorithms, pseudorandomness, expander graphs, error-correcting codes.
• Application Areas: Cryptography, Privacy.

• Recognize the fundamental mathematical problems at the root of modern computer science and its key applications in Data Science.

• Master the essential theoretical techniques which are used in analysing modern computer science problems.

• Face-to-face lectures

Lectures.

The exam has a theoretical part, assessing the students' knowledge of some fundamental results and related proof techniques, and some exercises indended to assess their ability to apply the acquired knowledge to specific circumstances.

The teaching materials are communicated before the beginning of the course.