Лекция
Руководитель и основатель компании MobileUp Сергей Денисюк рассказывает про текущее состояние Интернета вещей и о том, какие перспективы в сфере мобильной...
Прямая сумма задач и проблема Direct-sum для коммуникационной сложности. Информационная сложность протоколов. Решение проблемы Direct-sum для информационной...
Доказательство линейной нижней оценки вероятностной сложности предиката DISJ.
Страница лекции на CSClub
Энтропия пары случайных величин и ее связь с энтропиями самих случайных величин. Условная энтропия. Общая информация. Независимость и информация....
Задача префиксного двоичного кодирования символов данного алфавита с известными частотами. Нижняя оценка средней длины кода с помощью этропии Шеннона....
Связь безошибочной вероятностной, односторонней вероятностной и недетерминированной сложностей. Вероятностный безошибочный протокол для DISJnk и пример...
Покрытия нулей и единиц матрицы M(f) предиката f. Применение метода размера прямоугольников для оценки этого покрытия. Недетерминированная сложность предикатов...
Алгоритм Рейнголда. Надежные вычисления
Алгоритм Рейнголда: решение здачи USTCON на логарифмической памяти.
Построение надежных булевых схем из ненадёжных...
Генератор Нисана
Генератор Нисана и дерандомизация вычислений на логарифмической памяти.
Страница лекции на CSClub
Экстракторы случайности
Построение экстрактора случайности с помощью блуждания на экспандере. Повторное использование отработанной случайности.
Страница лекции...
Формальное определение детерминированных и вероятностных коммуникационных протоколов. Дерево протокола. Прямоугольники, соответствующие листьям дерева...
Верхняя оценка O(1) для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка O(log2n) вероятностной...
Рекурсивные конструкции спектральных экспандеров
Алгоритмически эффективные конструкции экспандеров. Случайное блуждание на экспандере и построение генераторов...
Зигзаг-произведение графов
Спектр тензорного произведения графов. Зигзаг произведение однородных графов. Оценка спектрального зазора для зигзаг-произведения....
Понятие детерминированного коммуникационного протокола (неформально). Тривиальные верхние оценки на коммуникационную сложность D(f) для произвольной функции f:...
