Пятница 04.09. Александр Смаль (ПОМИ): "Гипотеза XOR-KRW"
PDMI seminars
Тема: Гипотеза XOR-KRW
Место: Zoom
Время: 04.09.2020, 18:00
Докладчик: Александр Смаль (ПОМИ)
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$ является неотъемлемой чертой нашего подхода.
Для получения этого результата мы разработали метод преобразования нижних оценок на мультиплексор в нижние оценки для функций при помощи сведений к недетерминированной сложности и результатов из неклассических моделей вычисления: полудуплексных и частично полудуплексных моделей коммуникации.
Alexander V. Smal
--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/0000000000008b298d05adf2c58a%40google.com.