|
СЕМИНАРЫ |
Семинар лаборатории математической логики (Санкт-Петербург)
|
|||
|
Доказательство нижних оценок на размер формул для булевых функций методами коммуникационной сложности А. В. Смаль Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук |
|||
Аннотация: В докладе будет рассказано о серии результатов о различных подходах к доказательству нижних оценок на размер формул для булевых функций методами коммуникационной сложности. Сначала будет рассказано об улучшении работы Меира и Вигдерсона о предсказании битов строки при помощи семейств сертификатов. Улучшение позволяет получить альтернативное доказательство для точной нижней оценки на формулы формулы глубины три (имеются в виду формулы с гейтами неограниченной арности) для функций чётности и внутреннего произведения. Далее будет рассказано о гипотезе Карчмера - Раза - Вигдерсона и её варианте для композиции с мультиплексером. При рассмотрении этой задачи естественным образом возникает необходимость рассмотреть альтернативную модель вычисления для коммуникационной сложности. В качестве такой модели будет предложена концепция полудуплексной коммуникационной сложности и рассказано о результатах в этой области. В заключение будет рассказано о том, как с использованием полудуплексной коммуникационной сложности получить нетривиальную нижнюю оценку на композицию универсального отношения и некоторой функции. Ключевые слова: формульная сложность, коммуникационная сложность * Ссылка для подключения будет распространяться через рассылку семинара |