• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Bachelor 2020/2021

A Theorist's Toolkit

Area of studies: Applied Mathematics and Information 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

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

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

Assessment Elements

  • non-blocking Homeworks
  • non-blocking Colloquium
    There is no exam. The course grade is given according to the cumulative assessment.
  • non-blocking Test
Interim Assessment

Interim Assessment

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

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.