Bachelor 2020/2021

A Theorist's Toolkit

Type: Elective course (Applied Mathematics and Information Science)

Area of studies: Applied Mathematics and Information Science

Delivered by: Big Data and Information Retrieval School

Where: Faculty of Computer Science

When: 4 year, 3 module

Mode of studies: distance learning

Instructors: Alexey Milovanov, Vladimir V. Podolskii, Michael Vyalyi

Language: English

ECTS credits: 4

Contact hours: 44

Course Syllabus

Abstract

The goal of the course "Theorist’s Toolkit" is to give learners understanding of basic techniques and methods for solving and analyzing problems in theoretical computer science. The target audience of this course is students of the specialization "Theoretical Computer Science". Among all the various methods of theoretical computer science, we cover the most actively used in modern research in this area.

Learning Objectives

• The main goal of this course is to give students understanding of the basic methods and techniques used in research of theoretical computer science.
• It is suggested that students will be able to formulate theoretical computer science problems.
• It is expected to develop students' ability to solve problems by using the methods of theoretical computer science.
• Students are expected to master the basic definitions and facts of mathematics and theoretical computer science covered in the course.
• It is expected that students will know how to use basic methods of theoretical computer science.
• It is planned to develop students' skills of transition from discussing practical problems to their mathematical formulations and further analysis of the formulated mathematical problems.

Course Contents

• Probabilistic methods.
  Chernoff bound and applications. Generalization to dependent random variables.
• Boolean Fourier analysis.
  Basic notions, results and applications.
• Polynomial method.
  Representation of boolean functions by polynomials, applications to decision trees, boolean circuits and communication complexity.

Assessment Elements

• Homeworks
• Colloquium
  There is no exam. The course grade is given according to the cumulative assessment.
• Test

Interim Assessment

• Interim assessment (3 module)
  0.5 * Colloquium + 0.35 * Homeworks + 0.15 * Test

Bibliography

Recommended Core Bibliography

• Arora, S., & Barak, B. (2009). Computational Complexity : A Modern Approach. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=304712

Recommended Additional Bibliography

• Ryan O’Donnell. (2012). Analysis of Boolean Functions. Http://Www.Cs.Mcgill.ca/%7Edenis/Barbados2012.Pdf.