Сравнение коммуникационной, информационной и вопросной сложности Козачинский Александр Николаевич

Короткий опис

Козачинский, Александр Николаевич.Сравнение коммуникационной, информационной и вопросной сложности : диссертация ... кандидата физико-математических наук : 01.01.06 / Козачинский Александр Николаевич; [Место защиты: Московский государственный университет имени М.В. Ломоносова]. - Москва, 2019. - 81 с.

Оглавление диссертациикандидат наук Козачинский Александр Николаевич
1.1 Технические факты
1.1.1 Комбинаторика булева куба
1.1.2 Теория информации
1.1.3 Экспандеры
1.2 Коммуникационная сложность
1.2.1 Коммуникационный протоколы и их характеристики
1.2.2 Средняя коммуникационная длина и информационное разглашение
1.2.3 Вычисление функций и различные виды коммуникационной сложности
1.3 Вопросная сложность
2 Коммуникационная сложность задачи Gap Hamming Distance с односторонней ошибкой
2.1 Нижняя оценка
2.2 Верхняя оценка
2.2.1 НТ-протокол
2.2.2 Протокол для GHD(n, L, L + 1)
2.2.3 Модификация НТ-протокол а
2.2.4 Финальный протокол
3 Связь вопросной и коммуникационной сложности
3.1 Результаты
3.2 Доказательства
3.2.1 Доказательство теоремы
3.2.2 Вывод следствия
3.2.3 Доказательство предложения
3.2.4 Доказательство предложения
3.2.5 Доказательство предложения
3.2.6 Доказательство теоремы
4 Частные и общие случайные биты в информационной сложности
4.1 Общие и частные случайные биты в сжатии протоколов и формулировка нашего результата
4.2 Основная лемма
4.3 Завершение доказательства
5 Интерактивные аналоги теоремы Вольфа — Слепяна
5.1 Верхние и нижние оценки дня интерактивного аналога теоремы Вольфа -Слоняна: формулировки результатов
5.2 Верхняя оценка
5,3 Нижняя оценка
Заключение
Список литературы