Семинар по истории математики, 1 октября 2020 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар по истории математики, 1 октября 2020 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Городской семинар по теории вероятностей и математической статистике, 25 сентября 2020 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

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

Докладчик: Alexander Golovnev (Georgetown University, USA).

Тема: Polynomial Data Structure Lower Bounds in the Group Model.Abstract Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial () lower bound for an explicit range counting problem of convex polygons in (each with facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing---in particular, on the existence and partial derandomization of optimal \emph{binary} compressed sensing matrices in the polynomial sparsity regime (). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 24 сентября 2020, 16:00Место: Доклад состоится онлайн при помощи ZOOM.Докладчик: А. Л. Вернер и Л. А. Антипова (РГПУ им. Герцена)Тема: Пять типов однородных ориентируемых многогранников отрицательной кривизны с выпуклыми гранямиАннотация: 

Семейство однородных ориентируемых многогранников отрицательной кривизны состоит из пяти типов. О геометрии этих пяти типов многогранников и пойдёт речь в настоящем докладе. Мы будем говорить о таких многогранниках как в евклидовом пространстве $E^3$, так и гиперболическом пространстве $H^3$, используя модель Кэли – Клейна и рассматривая один и тот же многогранник в шаре Клейна и как многогранник пространства $E^3$, и как многогранник пространства $H^3$. При этом внутренние метрики многогранников в пространстве $H^3$ будут гладкими. Такие многогранники в $H^3$ мы будем называть кентаврами, имея в виду их двойственную природу – одновременно многогранность и гладкость.

 

Мы напомним, как строятся эти многогранники в $H^3$, построим замкнутые геодезические на этих многогранниках и исследуем плотность (density) их проекций на абсолют шара Клейна.

Семинар по истории математики, 3 сентября 2020 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар по истории математики, 3 сентября 2020 г. 18:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Семинар по истории математики, 3 сентября 2020 г. 17:00, г. Санкт-Петербург, ПОМИ, Фонтанка 27, ауд. 106

Пятница, 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, из её доказательства будет следовать, что . Кроме того, будет сформулировано ослабление XOR-KRW гипотезы, доказательство которой повлечёт суперкубическую нижнюю оценку на формульную сложность в базисе Де Моргана.

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

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

Пятница, 28 августа, Zoom. Начало в 18:00.

Докладчик: Артур Игнатьев (СПбГУ).

Тема: Новые оценки на полудуплексную коммуникационную сложность.Abstract В докладе будет рассказываться про новые оценки на коммуникационную сложность в полудуплексной модели коммуникации. Полудуплексная коммуникационная модель - это обобщение классической модели коммуникационной сложности, предложенной Яо. Общение в такой полудуплексной модели напоминает общение по рации: в каждый момент времени каждый игрок находится либо в состоянии передачи сообщения, либо в состоянии приёма. При этом, если оба игрока передают сообщение одновременно, то они не слышат друг друга, а сообщения теряются. Мотивация для изучения данной модели происходит из исследований KRW гипотезы для композиции функции и мультиплексера. В докладе будет рассказано о новых верхних и нижних оценках для функции , а также для игр Карчмера-Вигдерсона для функций подсчёта по модулю и рекурсивной функции большинства. Кроме того, будет сформулировано определение недетерминированной полудуплексной коммуникационной сложности и доказаны оценки, связывающие её с классической недетерминированной коммуникационной сложностью.

По материалам статьи: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov, "New bounds on the half-duplex communication complexity" (https://eccc.weizmann.ac.il/report/2020/117/)

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.

Пятница, 7 августа, Zoom. Начало в 11:00.

Докладчик: Ярослав Алексеев (СПбГУ).

Тема: Нижняя оценка для обобщения системы PC и моделирование системы Res-Lin.Abstract Мы рассмотрим обобщение системы Polynomial Calculus, в котором дополнительно можно извлекать квадратный корень из многочлена и вводить новые переменные, записывающие многочлены от исходных переменных. Мы докажем экспоненциальную нижнюю оценку на размер опровержения в этой системе равенства (), при этом для доказательства нижней оценки на размер доказательства нам не потребуется нижняя оценка на степень. Благодаря тому, что эта система полиномиально моделирует Res-Lin (систему, оперирующую дизъюнкциями линейных уравнений; введена Разом и Цамеретом), мы получим альтернативное доказательство нижней оценки Парта и Цамерета на размер доказательств в Res-Lin.

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.

Пятница, 31 июля, Конференция Zoom. Начало в 17:00.

Докладчик: Виталий Демьянюк.

Тема: Теоретические оценки качества и сложности алгоритмов в дизайне сетевых элементов.Abstract В современных сетях число пользователей растет экспоненциально, структура сети становится все более сложной, а количество поддерживаемых стандартов постоянно увеличивается. Все это приводит к тому, что состояние сети становится сложным по структуре. С другой стороны, требования эффективности тоже быстро растут (обработка одного пакета должна происходить на уровне десятков или сотен наносекунд). В результате нужно искать компромисс между выразительностью представления состояния сети и эффективностью обработки пакетов. В первой части мы рассмотрим три проекта, посвящённых эффективному представлению программ, обрабатывающих пакеты. Во второй части мы покажем, как можно использовать ресурсы всей сети для задачи мониторинга трафика, уменьшающего локальный размер состояния в каждом отдельном элементе.

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.

Вторник, 30 июня, Zoom. Начало в 18:30.

Докладчик: Yuri Gurevich (University of Michigan).

Тема: What, if anything, can be done in linear time?Abstract The answer to the title question seems to be "Not much." Even sorting n items takes n x log(n) swaps. But, in fact, quite a bit can be done in linear time. We start with an illustration of linear-time techniques. Then we sketch the linear-time decision algorithm for propositional primal infon logic. Finally we mention useful extensions of that logic decidable in deterministic or probabilistic linear time.

Вторник, 23 июня, Zoom. Начало в 18:30.

Докладчик: Graham Priest (Graduate Center, City University of New York).

Тема: Perspectives on the Universe.Abstract Joel Hamkins has advanced a well known view to the effect that there is no unique universe of sets. There is simply a plurality of such universes. We have, then, a pluriverse. A natural objection to this view is that there is still a single universe: the totality, V, in which all the members of the pluriverse find themselves. In this paper I consider a reply to the objection, to the effect that there is no such thing as V in itself. Rather, each member of the pluriverse simply gives a different perspective on what V is like. This view is then generalised in the light of mathematical pluralism. What emerges is a vastly expanded, and logic-neutral view of the pluriverse.

Вторник, 16 июня, Zoom. Начало в 18:30.

Докладчик: Heinrich Wansing (Ruhr-Universität Bochum).

Тема: An Extension of Connexive Logic C.Abstract The connexive logic C is a simple variant of Nelson's Logic N4, obtained by making a small change in the falsification clause for the conditional. This was an important step marked in the field of connexive logic since C can be seen as the first system of connexive logic with an intuitively plausible semantics. The aim of the present paper is to consider an extension of C obtained by adding the law of excluded middle with respect to the strong negation. The extension of C is motivated by three questions. The first question comes from a system CN devised by John Cantwell. The second question concerns how many more connexive theses, beside the basic theses of Aristotle and Boethius, can be captured within the framework suggested in the above paper. The third question addresses the relation between constructivity and the law of excluded middle. We will show that the quantified version of our extension of C satisfies the Existence Property and its dual, but fails to satisfy the Disjunction Property and its dual when the law of excluded middle is restricted to atomic formulas.

Пятница, 5 июня, Zoom. Начало в 16:00.

Докладчик: Дмитрий Соколов (СПбГУ, ПОМИ).

Тема: Нижние оценки на систему AC_0-Frege.Abstract В этом докладе мы обсудим детали доказательства нижней оценки на систему доказательств AC_0-Frege. Нашей основной целью будет разобраться в технических деталях switching леммы для паросочетаний из классической статьи Urquhart, Fu ``Simplified Lower Bounds for Propositional Proofs''.

Классическое определение коммуникационного протокола использует фиксированное разбиение входных переменных на 2 множества $X\cup Y = M$. Мы рассмотрим естественное обобщение, в котором протокол может недетерминированно выбирать между $k$ различными подпротоколами, каждый из которых использует разное разбиение $f_1(X_1, Y_1)$, ... $f_k(X_k, Y_k)$, определим multi-partition communication complexity, и изучим её связь с нижними оценками на сложность однопроходных ветвящихся программ.

Первая статья Колмогорова 1965 года указывала "три подхода к определению количества информации" - комбинаторный (логарифм мощности), вероятностный (шенноновская энтропия) и алгоритмический (длина кратчайшего описания). Эта возможность перевода с одного языка на другой многократно оказывалась полезной: скажем, теорема Харпера о множестве с минимальной окрестностью в булевом кубе была переформулирована (Бюрман, Верещагин, Фортноу и др.) как возможность увеличить колмогоровскую сложность изменением некоторой доли битов.

Задача (n,3)-MAX-SAT является частным случаем задачи MAX-SAT с дополнительным ограничением на входную формулу, что каждая переменная встречается в формуле не более трех раз. Мы рассмотрим различные параметризации этой задачи, улучшим известные ранее верхние оценки на время решения (n,3)-MAXSAT относительно числа переменных в формуле, а также относительно числа клозов, которые мы хотим выполнить.
Кроме того, мы покажем, что выполнить хотя бы на один клоз больше, чем при тривиальном означивании, где всем переменным присваивается истина, уже является NP-трудной задачей.

Dag-like коммуникационные протоколы — обобщение классических коммуникационных протоколов. С их помощью можно перенести нижние оценки на ширину резолюционного доказательства невыполнимой формулы на другие системы доказательств, а также на размер монотонных схем для некоторых связанных задач. Для этого используется техника lifting — вместо каждой переменной формулы подставляется некоторая функция от новых переменных, так называемый гаджет. Однако известные гаджеты, подходящие для этой техники, имеют большой размер. Вопрос, можно ли использовать гаджет константного размера, является открытым.