Courses Computer Science Club, spring 2017, part two

We continue to upload videos of the courses of the Computer Science Club at POMI RAS. The first part is here . There are four courses in this compilation: “Communication complexity”, “Expanders and their applications”, “Machine translation” and “Selected chapters of the theory of flows”.

Communication complexity

Lecturer :
Nikolai Konstantinovich Vereshchagin, professor of Moscow State University, member of the European Academy.

annotation
The simplest model in the theory of communication complexity is as follows. There are two participants (computer or person) who together want to solve some problem. None of them can solve the problem on their own (for example, each of them does not have enough data or resources). Therefore, they need to communicate. Communication complexity measures the minimum possible number of bits that participants need to exchange to solve a problem. The time required to conduct local calculations by each of the participants is not taken into account - this is a fundamental difference from the theory of the complexity of calculations. The results of communication complexity are very widely used in other areas of theoretical computer science.
')
Materials and video course.

Expanders and their applications

Lecturer :
Andrei Evgenyevich Romashchenko, Researcher at the Institute for Information Transmission Problems of the Russian Academy of Sciences in Moscow and the Laboratory for Informatics, Robotics and Microelectronics (LIRMM) in Montpellier.

annotation
Expanders (expanding graphs) are powerful and highly sophisticated tools of theoretical informatics and discrete mathematics. Apparently, the efficiency of expanders is partly due to the fact that they (by their very definition) make it possible to naturally combine combinatorial-geometric, algebraic, and probabilistic reasoning. Expanders were identified in the 1970s. Over the past 30 years, they have found many beautiful uses. Expanders are used in various designs of derandomization. With the help of expanders, error correction codes and reliable computational schemes are built. The expander technique is used in various proofs of the theory of the complexity of computations (for example, in the proof of the famous PCP theorem). In this course we will be interested in expanders from the point of view of the theory of algorithms. We will study the relationship between the combinatorial and spectral properties of expander, consider effective algorithmic methods for constructing such graphs, and also discuss the various applications of expanders. We will also talk about the relationship of expanders with other remarkable classes of graphs: extractors, dispersors, compressors.

Materials and video course.

Machine translate

Lecturer :
David Talbot, Lead Researcher at Google in the UK, Lecturer at the School of Data Analysis.

annotation
The first day of the course introduces students to the problem of machine learning with parallel data for automatic translation. Listeners will be asked to implement simple algorithms for word alignment. The second day of the course will be devoted to the basics of neural machine translation. Students will be able to gain hands-on experience with a simple codec model. Initial Python skills and the ability to compile and run code from github will be useful. The course is read in English.

Materials and video course.

Selected chapters of the theory of flows

Lecturer :
Maxim Alexandrovich Babenko, Associate Professor at the Higher School of Economics, Lecturer at the School of Data Analysis, Officer Yandex.

annotation
The theory of flows, without a doubt, is one of the most well studied sections of combinatorial optimization, having a variety of applications, both theoretical and practical. The course will begin with a brief introduction to the subject in which we will examine the basic algorithms for the maximum flow problem, and then quickly move on to more modern topics: pushing through the preflow and parametric flow problems. In the final part of the course, let us touch upon the generalizations of the notion of flow: we study the simplest types of multi-stream problems, and also talk about flows in the skew-metering and bidirectional graphs. The listeners are supposed to become acquainted with the basic concepts of algorithmic graph theory.

Materials and video course.