Будет рассказан недавний алгоритм Бьорклунда, Хусфельда, Каски, Коивисто решения задачи нахождения просто пути длины k в неориентированном графе за время O^*(2^{3k/4}). Из этого, в частности, следует, что найти гамильтонов путь в неориентированном графе можно быстрее 2^n. Алгоритм основан на построении специального многочлена, в котором каждому простому k-пути соответствует уникальный моном, а самопересекающиеся k-пути разбиваются на пары с одинаковыми мономами. Таким образом, данный многочлен тождественно равен нулю в поле характеристики два (достаточно большого размера) тогда и только тогда, когда в графе есть простой k-путь.

В докладе мы рассмотрим булевы схемы, в которых входная степень гейта ограничена линейной функцией от числа переменных. Мы докажем оценку \Omega(log^2 n) на явную функцию для подобных схем. Будет продемонстрирован метод применения коммуникационной сложности для доказательства нижних оценок на размер схем.

In this lecture we will survey the area of online algorithms using some well known examples and problems. We will look at classical approaches as well as new ones, and discuss the underlying principles and objectives that drive research in the online paradigm.