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

Лекция 10
Communication Complexity

What: Lecture
When: Sunday, 08 March 2009, 14:00–15:30
Where: ПОМИ РАН

Description

Нижняя оценка \( ST=\Omega(n^2) \) для зоны \( S \) и времени работы многоленточной машины Тьюринга, распознающей палиндромы. Квадратичная нижняя оценка на время распознавания палиндромов на одноленточной машине Тьюринга. Детерминированная сложность \( D^{best}(f) \) булевой функции \( f \) (минимальная из сложностей \( D(f) \) по всем разбиениям множества входных битов на две равных части). Оценка \( D^{best}(f) \) для функции циклического равенства. Нижняя оценка \( (\sqrt A)T>D^{best}(f) \) для площади \( А \) и времени работы \( T \) микросхемы, вычисляющей булеву функцию \( f \).

Video