City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 7. Параллельное умножение и сложение. Коммуникационная сложность.
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 26 October 2020, 22:30–23:50
Where: Конференция в zoom, Онлайн

Description

Сложение двух n-битных чисел схемой размера \(O(n)\) и глубины \(O(\log n)\). Умножение двух n-битных чисел схемой размера \(O(n^2)\) и глубины \(O(\log n)\).

Коммуникационные протоколы, комбинаторные прямоугольники. Коммуникационная сложность предиката равенства. Компромисс между временем и памятью для машины Тьюринга, решающей задачу о палиндроме.

Video

Other materials

Текущая версия конспекта.