Пятница, 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 $](../../../sites/default/files/tex/9711f8275598f05ca25ac95f35bccbf9d2328e01/index.png)
. Кроме того, будет сформулировано ослабление XOR-KRW гипотезы, доказательство которой повлечёт суперкубическую нижнюю оценку на формульную сложность в базисе Де Моргана.
Изучение этой гипотезы позволило нам частично ответить на открытый вопрос, сформулированный в статье Гавинского и др. [GMWW17] касательно композиции универсального отношения и функции. Если быть более точным, то мы покажем, что существует функция
![$ g $](../../../sites/default/files/tex/7c5d55e3abc26365f64db1b220fd6b1df78da41e/index.png)
, такая что композиция универсального отношения и
![$ g $](../../../sites/default/files/tex/7c5d55e3abc26365f64db1b220fd6b1df78da41e/index.png)
значительно сложнее, чем универсальное отношение. Тот факт, что мы можем доказать лишь факт существование
![$ g $](../../../sites/default/files/tex/7c5d55e3abc26365f64db1b220fd6b1df78da41e/index.png)
является неотъемлемой чертой нашего подхода.
Для получения этого результата мы разработали метод преобразования нижних оценок на мультиплексор в нижние оценки для функций при помощи сведений к недетерминированной сложности и результатов из неклассических моделей вычисления: полудуплексных и частично полудуплексных моделей коммуникации.
Видео:
https://www.youtube.com/watch?v=LMGx4OY0jZ0