We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.

✖
  • A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedFor visually-impairedUser profile (HSE staff only)SearchMenu
HSE University
User profile (HSE staff only)Search
Advanced search

Course Syllabus

Course Syllabus


 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Bachelor 2024/2025

Computational Complexity Theory

Type: Elective course (Software Engineering)
Area of studies: Software Engineering
Delivered by: Big Data and Information Retrieval School
Where: Faculty of Computer Science
When: 4 year, 1-3 module
Mode of studies: offline
Open to: students of all HSE University campuses
Instructors: Bruno Frederik Bauwens, Yaroslav Ivanashev
Language: English
ECTS credits: 10

Course Syllabus

Ask Question

Abstract

This course teaches a mathematical theory that helps to invent better algorithms. With “better” we mean that the algorithms use fewer resources such as time or memory. We also consider parallel computation, distributed systems and learning problems. In these settings we might also optimize other types of resources. For example, in distributed systems we might want to minimize the amount of communication. We focuss on worst case guarantees. A large part of our time is devoted to the study of what is not possible. In other words, we study fundamental barriers for the existence of programs that use fewer resources than a given bound.