Вторник, 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 июня, Zoom. Начало в 18:30.

Докладчик: В.Я. Крейнович (Университет Техаса в Эль-Пасо).

Тема: Модальная математика и рассуждения в условиях интервальной неопределённости.Abstract Как мы можем делать заключения о реальном мире? Как мы можем предсказать будущее? В идеализированной ситуации, когда мы можем всё померить с идеальной точностью, единственная проблема — как решить соответствующие уравнения. На основе этих решений мы всё и предскажем. В реальной жизни точность измерений ограничена. Часто единственное, что мы знаем о погрешности измерений, — это верхняя граница абсолютной величины этой погрешности. В этом случае единственное, что мы знаем после измерения, — это интервал возможных значений измеряемой величины. При такой интервальной неопределённости для многих свойств мы не можем сказать, выполняется это свойство или нет; иногда мы можем заключить, что точно выполняется, а иногда мы только знаем, что может быть выполняется, а может быть нет — значит надо использовать модальную логику (точнее модальную математику). И всё это надо вычислять, так что надо использовать методы конструктивной и вычислительной математики (и учитывать при этом вычислительную сложность). В докладе мы покажем, как всё это соединяется вместе в интервальной математике. Юрий Матиясевич, один из пионеров этого направления, пришёл туда из конструктивной математики, поэтому для него интервальные вычисления — это прикладная конструктивная математика, но с таким же успехом их можно назвать прикладной модальной математикой.

Видеозапись:
https://youtu.be/59jKSoHkQsU

Ссылка на Math-Net.Ru:
http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=27141

ПриложениеПрезентация

Петербургский топологический семинар им. В. А. Рохлина, 27 мая 2020 г. 17:15, г. Санкт-Петербург, Zoom channel 511 327 649

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 28 мая 2020, 16:00Место: Доклад состоится онлайн при помощи ZOOM.Докладчик: С. В. Буяло (ПОМИ)Тема: Уравнение для мебиусовых структур: симметрии двойных отношений и итерированные системы функцийАннотация: 

Будет рассказано о сюрпризах, которые возникают при попытке деформировать мебиусовы структуры: представления симметрической группы $S_5$ и итерированные системы функций.

Пятница, 29 мая, Zoom. Начало в 18:10.

Докладчик: Артур Рязанов (ПОМИ РАН).

Тема: Нижние оценки на коммуникационную сложность задач поиска с гаджетом четности и без гаджета.Abstract В теории сложности доказательств часто рассматривается такая задача поиска: дана невыполнимая формула в КНФ и набор значений ее переменных, требуется найти дизъюнкт формулы, который опровергается этим значением переменных. Известно, что доказательство невыполнимости формулы во многих древовидных системах доказательств можно перестроить в вероятностный коммуникационный протокол для этой задачи поиска. Тем самым для доказательства нижней оценки на сложность древовидного вывода достаточно доказать нижнюю оценку на коммуникационную задачу. Мы будем рассматривать вероятностную коммуникационную сложность для двух участников и k участников в модели "число на лбу".

Первую нижнюю оценку на вероятностную коммуникационную сложность задач поиска получили Бим, Питасси и Сегерлинд (2007), затем Гёс и Питасси (2013) получили более простое доказательства нижней оценки на коммуникационную сложность задачи поиска через его критическую блочную чувствительность. Оба этих результата использую искусственные формулы: в традиционную формулу добавляется гаджет, то есть каждая переменная в формуле заменяется на функцию от свежих переменных, значения которых разделяются между участниками коммуникационного протокола. Мы предлагаем новый способ доказательства нижних оценок на коммуникационную сложность задач поиска, который позволяет получать нижние оценки на естественные формулы.
Таким образом, мы доказываем:
* Точную экспоненциальную нижнюю оценку на сложность опровержения принципа совершенного паросочетания для полного двудольного графа в системе Res().
* Экспоненциальную нижнюю оценку на сложность бинарного принципа Дирихле для древовидных систем, оперирующих строками доказательств, которые можно вычислить с небольшой вероятностной коммуникацией.

Доклад основан на совместной работе с Д. Ицыксоном.

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

Пятница, 22 мая, Zoom. Начало в 18:10.

Докладчик: Артур Рязанов (ПОМИ РАН).

Тема: Применение критерия Юкны для нижних оценок в системе доказательств Cutting Planes.Abstract Это продолжение предыдущего доклада. Мы рассмотрим взвешенный критерий Стасиса Юкны для доказательства нижних оценок на монотонную вещественную схемную сложность. Затем мы покажем, как его применить для доказательства экспоненциальной нижней оценки на сложность опровержения бинарного принципа Дирихле в системе доказательств Cutting Planes (результат Павла Пудлака и Павла Грубеша).

Видео доклада: https://www.youtube.com/watch?v=rz1LjaZSu7c

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 21 мая 2020, 16:00Место: Доклад состоится онлайн при помощи ZOOM.Докладчик: А. Л. Вернер и Л. А. АнтиповаТема: Невыпуклые однородные многогранники с выпуклыми гранямиАннотация: 

Старший автор занимался невыпуклыми многогранниками ещё более полувека тому назад. В 2016 году он вместе с М.Н.Васильевой и О.Г.Даниловой
рассказывал на Александровском семинаре о правильных невыпуклых
многогранниках Кеплера и Пуансо, а в 2018 году они же рассказывали о
некоторых невыпуклых однородных многогранниках. У однородных
многогранников все многогранные углы в вершинах равны друг другу.
 

В этом учебном году мы с Л.А.Антиповой изучали невыпуклые однородные
многогранники с выпуклыми гранями. Их оказалось 16 типов, два из которых
это многогранники Пуансо – большой икосаэдр и большой додекаэдр. Один из этих типов – многогранники, изометриченые плоскому тору, три типов этих многогранников имеют положительную кривизну, а 12 типов –  отрицательную кривизну.  Мы кратко расскажем о геометрии каждого из типов, а двум самым сложным из них – большому ромбокубооктаэдру и большому икосоикосододекадру – уделим большее внимание. Основные вопросы, которыми мы занимались, были построение этих
многогранников и их ориентируемость.

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

Докладчик: А.С. Морозов (Институт математики им. С.Л. Соболева СО РАН).

Тема: О -определимых структурах в HF(R).Abstract Доклад представляет собой обзор результатов об алгебраических структурах, -определимых в наследственно конечной надстройке над вещественными числами, HF(R), являющейся частным случаем допустимых множеств. Это понятие можно рассматривать как одно из обобщений классического понятия вычислимой структуры на ситуацию, когда в качестве основного множества рассматривается множество всех мыслимых конечных программистских конструкций типа `список', `массив', `конечное множество', `конечный граф' и т.п., а в качестве вычислимости — возможность определить функции в некотором алгоритмическом языке высокого уровня, позволяющего вычислять основные операции над R, находить и использовать в дальнейших вычислениях корни уравнений.

Приводятся общие результаты о -определимых структурах и подмножествах HF(R), а также примеры и некоторые общие методы доказательства неопределимости различных структур.

Пятница, 15 мая, Zoom. Начало в 18:10.

Докладчик: Артур Рязанов (ПОМИ РАН).

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

У доклада планируется продолжение, в котором мы обсудим применение критерия Юкны для получения нижних оценок на сложность доказательств в системе Cutting Plane.

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

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

Докладчик: Ф.Н. Пахомов (Математический институт им. В.А. Стеклова РАН).

Тема: О полноте трансфинитных итераций схем рефлексии.Abstract Для достаточно сильных арифметических теорий T можно определить схему равномерной рефлексии RFN(T), выражающую тот факт, что всякое предложение доказуемое в T истинно. В силу второй теоремы Гёделя о неполноте, теории T+RFN(T) сильнее, чем T для непротиворечивых теорий T. Прогрессия Тьюринга-Фефермана T_a — это трансфинитная прогрессия усиливающихся теорий, начинающаяся с T_0=T, где каждая следующая теория получается путём добавления схемы равномерной рефлексии к предшествующей. Как было установлено С. Феферманом, всякое истинное арифметическое предложение является теоремой PA_a для подходящего a.

В первой половине настоящего доклада я познакомлю слушателей с прогрессиями Тьюринга-Фефермана и расскажу о некоторых их приложениях. Во второй половине доклада я познакомлю слушателей с новым простым доказательством упомянутой выше теоремы Фефермана и некоторыми новыми результатами вокруг неё. Доклад основан на совместной работе с Д. Россеггерром и М. Ратьеном.

Пятница, 8 мая, Zoom. Начало в 18:10.

Докладчик: Н. Карпов (Indiana University).

Тема: Collaborative Top Distribution Identifications with Limited Interaction.Abstract В докладе мы рассмотрим задачу поиска среди n распределений m распределений с наибольшим средним. В литературе про обучении с подкреплением эта задача известка как top-m arm identifications и имеет много применений. Мы рассмотрим модель когда несколько игроков пытаются решить задачу в коллаборации. Я расскажу о нашем недавнем результате в котором мы достигаем оптимального trade-off между количеством раундов коммуникации между игроками и числом сэмплов необходимых для решения задачи совместно. В частности я рассажу как сложность задачи поиска m лучших распределений отличается от сложности поиска лучшего распределения.

Доклад будет основан на совместной работе с Qin Zhang и Yuan Zhou: https://arxiv.org/abs/2004.09454 .

Доклад пройдет в Zoom https://iu.zoom.us/j/99855408465?pwd=b1VVTnZMaHFmdzBzVEJsWEd4UjlFZz09

Meeting ID: 998 5540 8465
Password: top100

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

Доклад по одноимённой работе Jérémie Chalopin, Victor Chepoi, Anthony Genevois, Hiroshi Hirai, and Damian Osajda

https://arxiv.org/abs/2002.06895.

Петербургский топологический семинар им. В. А. Рохлина, 27 апреля 2020 г. 17:15, г. Санкт-Петербург, zoom 958-115-833 ("102 аудитория" ФМКН СПбГУ)

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

Докладчик: С.А. Дробышевич (ИМ СО РАН).

Тема: Системы с явными опровержениями.Abstract В ходе доклада будет предложен аналог отношений следования Тарского для систем с явными опровержениями, а также адаптации некоторых простых понятий и техник для них. Системы с явными опровержениями отличаются тем, что опровержения в них выражаются не (только) при помощи связки отрицания в логическом языке, но, в некотором смысле, стоят на равных правах с предикатами истинности/доказуемости. Интерес к таким системам тесно связан с логическим билатерализмом — позицией, в рамках которой для объяснения смысла логической связки нужны не только условия на доказуемость утверждений, имеющих эту связку в качестве основной, но и условия на опровержимость подобных утверждений. Хотя в литературе почти не встречаются системы такого вида, некоторые известные системы (например, логики Нельсона) можно интерпретировать как системы с явными опровержениями. В качестве одного интересного примера будет рассмотрена 2-интуиционистская логика Хайнриха Вансинга — система, в языке которой совсем нет отрицания, но явным образом присутствуют опровержения.

Важное примечание: Информация о том, как именно будет организовано заседание в Zoom, будет разослана отдельным письмом.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 23 апреля 2020, 16:00Место: Доклад состоится онлайн при помощи ZOOM.Докладчик: В. ЗолотовТема: Билипшицевы вложения (слабо)-самосжимамающихся кривых в евклидовы пространстваАннотация: 

Вопрос о характеризации метрических пространств допускающих биипшицевые ввложения в евклидовы пространства неподдается познанавательным нападкам математического сообщества.

В докладе я хочу рассказать решение одномерной версии этого вопроса, где под одномерностью я имею в виду, что вкладываемое пространство можно представить как образ самосжимающейся кривой.

Cреда, 22 апреля, Zoom meeting. Начало в 18:10.

Докладчик: В.В. Подольский (МИАН, НИУ ВШЭ).

Тема: Вычисление функций голосования монотонными формулами маленькой глубины.Abstract Известно, что функцию голосования от n переменных можно вычислить булевой формулой логарифмической глубины, состоящей из функций голосования от трех переменных. До недавнего времени была известна только вероятностная конструкция такой формулы. В докладе мы расскажем о явной конструкции. Этот результат дает положительный ответ на гипотезу из работы Cohen et al (CRYPTO 2013). Если останется время, мы также обсудим обобщение игр Карчмера-Вигдерсона на число игроков, большее двух, и связь этой модели с пороговыми схемами.

Доклад основан на совместной работе с Александром Козачинским: https://eccc.weizmann.ac.il/report/2020/017/

Доклад пройдет в Zoom, необходима регистрация. Для регистрации пройдите по ссылке.
https://zoom.us/meeting/register/tJcucemuqD0oGtLqf7hoIiurxtIqW9P_QRs-
После регистрации вы получите подтверждение по почте с информацией о докладе.

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

Докладчик: Д. Рогозин (Московский государственный университет им. М.В. Ломоносова).

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

Важное примечание: Информация о том, как именно будет организовано заседание в Zoom, будет разослана отдельным письмом.