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

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

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

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

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

Докладчик: Пётр Смирнов.

Тема: Квазиполиномиальные опровержения цейтинских формул в Cutting Planes.Abstract В докладе для любой цейтинской невыполнимой формулы на графе G мы построим опровержение в системе Cutting Planes (CP) длины , где n — число вершин графа G, а D — его максимальная степень.

Опровержение строится следующим образом: мы рассматриваем (построенное ранее в другой работе) квазиполиномиальное опровержение в более сильной системе Stabbing Planes, замечаем структурное свойство этого опровержения, а затем перестраиваем любое опроверждение с таким свойством в систему CP.

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

Доклад основан на статье Daniel Dadush и Samarth Tiwari «On the Complexity of Branching Proofs» [https://homepages.cwi.nl/~dadush/papers/branching.pdf].

Ссылка на конференцию Zoom будет отправлена за пару часов до доклада.

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

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 1 октября 2020, 16:00Место: Доклад состоится онлайн при помощи ZOOM.Докладчик: Г. Ю. Панина (ПОМИ)Тема: Цветная топологическая теорема ТвербергаАннотация: 

Возьмите  теорему Радона (всякое множество из  d+2  точек d-мерного пространства может быть разделено на два непересекающихся подмножества, чьи выпуклые оболочки пересекаются),  потребуйте бОльшей кратности пересечения, ослабьте аффинный вариант до произвольного непрерывного, добавьте цвета -- получится цветная топологическая  теорема Тверберга. Ожидаемо, что требуя больше, придется дополнительно заплатить.  Интересно, что добавление цветов бесплатно в предроложении, что требуемая кратность пересечения -- простое число.

 

У этой теоремы есть два  доказательства -- первое (Благоевич, Циглер, Матшке), через эквивариантные препятствия, и второе (Вречица, Живалевич) -- через степень эквивариантных отображений.

 

Я расскажу второе доказательство,  основанное на теореме о степени эквивариантного отображения   и представлю один совсем новый результат (Йойич, Живалевич, П), который говорит  о том, что можно сделать, если требуемая кратность пересечения -- степень простого  числа.

Пятница, 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.

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