Home

Пятница 04.09. Александр Смаль: "Гипотеза XOR-KRW"

Пятница, 4 сентября, Zoom. Начало в 18:00.

Докладчик: Александр Смаль (ПОМИ).

Тема: Гипотеза XOR-KRW.

Abstract

Доклад по статье Ivan Mihajlin, Alexander Smal, "Toward better depth lower bounds: the XOR-KRW conjecture" https://eccc.weizmann.ac.il/report/2020/116/

В этом докладе будет рассказано про новую гипотеза XOR-KRW, которая является ослаблением гипотезы Карчмера-Раза-Вигдерсона [KRW95]. Не смотря на то, что эта гипотеза более слабая, чем гипотеза KRW, из её доказательства будет следовать, что $ P\not\subseteq NC_1 $. Кроме того, будет сформулировано ослабление XOR-KRW гипотезы, доказательство которой повлечёт суперкубическую нижнюю оценку на формульную сложность в базисе Де Моргана.

Изучение этой гипотезы позволило нам частично ответить на открытый вопрос, сформулированный в статье Гавинского и др. [GMWW17] касательно композиции универсального отношения и функции. Если быть более точным, то мы покажем, что существует функция $ g $, такая что композиция универсального отношения и $ g $ значительно сложнее, чем универсальное отношение. Тот факт, что мы можем доказать лишь факт существование $ g $ является неотъемлемой чертой нашего подхода.

Для получения этого результата мы разработали метод преобразования нижних оценок на мультиплексор в нижние оценки для функций при помощи сведений к недетерминированной сложности и результатов из неклассических моделей вычисления: полудуплексных и частично полудуплексных моделей коммуникации.

Видео: https://www.youtube.com/watch?v=LMGx4OY0jZ0