Лекция
На мастер-классе эксперты «Сбербанк-Технологии» Артем Соковец и Иван Варивода рассказывают, зачем нужна автоматизация, когда следует ее начинать и какие шаги...
Руководитель и основатель компании MobileUp Сергей Денисюк рассказывает про текущее состояние Интернета вещей и о том, какие перспективы в сфере мобильной...
Алгоритм Рейнголда. Надежные вычисления
Алгоритм Рейнголда: решение здачи USTCON на логарифмической памяти.
Построение надежных булевых схем из ненадёжных...
Экстракторы случайности
Построение экстрактора случайности с помощью блуждания на экспандере. Повторное использование отработанной случайности.
Страница лекции...
Генератор Нисана
Генератор Нисана и дерандомизация вычислений на логарифмической памяти.
Страница лекции на CSClub
Зигзаг-произведение графов
Спектр тензорного произведения графов. Зигзаг произведение однородных графов. Оценка спектрального зазора для зигзаг-произведения....
Рекурсивные конструкции спектральных экспандеров
Алгоритмически эффективные конструкции экспандеров. Случайное блуждание на экспандере и построение генераторов...
Вершинное и рёберное расширение графа
Лемма об уединённых соседях. Декодирование экспандерного кода (параллельный алгоритм с логарифмическим числом итераций)....
Спектр графа, определение спектрального экспандера
Собственные числа и собственные векторы однородного графа. Поведение спектра при возведении графа в степень...
Спектр случайного графа. Случайное блуждание на экспандере
Теорема о существовании спектральных экспандеров с параметрами (n=d4,d,γ). Оценка спектра для...
Комбинаторные экспандеры: определения и теоремы о существовании
Комбинаторные определения экспандера (для однородного и для двудольного графов). Вероятностное...
Примеры применений комбинаторных экспандеров
Два примеры применения экспандеров:
Энтропия пары случайных величин и ее связь с энтропиями самих случайных величин. Условная энтропия. Общая информация. Независимость и информация....
Доказательство линейной нижней оценки вероятностной сложности предиката DISJ.
Страница лекции на CSClub
Прямая сумма задач и проблема Direct-sum для коммуникационной сложности. Информационная сложность протоколов. Решение проблемы Direct-sum для информационной...
Связь безошибочной вероятностной, односторонней вероятностной и недетерминированной сложностей. Вероятностный безошибочный протокол для DISJnk и пример...
Задача префиксного двоичного кодирования символов данного алфавита с известными частотами. Нижняя оценка средней длины кода с помощью этропии Шеннона....
Формальное определение детерминированных и вероятностных коммуникационных протоколов. Дерево протокола. Прямоугольники, соответствующие листьям дерева...
Покрытия нулей и единиц матрицы M(f) предиката f. Применение метода размера прямоугольников для оценки этого покрытия. Недетерминированная сложность предикатов...
Мастер-класс руководителя разработки в отделе развития платежей «Сбербанк-Технологии» Станислава Кима.
Верхняя оценка O(1) для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка O(log2n) вероятностной...
Понятие детерминированного коммуникационного протокола (неформально). Тривиальные верхние оценки на коммуникационную сложность D(f) для произвольной функции f:...
Страницы
- « первая
- ‹ предыдущая
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »