#матлог #учёба #просеминар

💥В среду 24 сентября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Диагональные конструкции (добавка)" (А.А.Оноприенко).
✨Аннотация. Диагональная конструкция — традиционное название для ситуации, когда искомый объект строится шаг за шагом. Мы разберём применения такой конструкции в теории вычислимости.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 diagonal_2_2025.pdf

➰ ВК

#матлог #учёба #спецкурс

В осеннем семестре 2025/2026 учебного года Николай Константинович Верещагин прочитает спецкурс по выбору кафедры "Односторонние функции и их применения".

Спецкурс будет читаться по вторникам с 18:30 до 20:05. Первая лекция - 7 октября.

Страница спецкурса в базе мехмата: https://scs.math.msu.ru/ru/node/8576

➰ ВК

#матлог #спецсеминар #ллфф

24 сентября (среда) в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View»

Тема доклада: Классические и интуиционистские кондициональные логики: метатеория, семантика, теория доказательств​​ (часть 1)

Докладчик: Игорь Зайцев (стажер-исследователь МЛ ЛогЛинФФ)

Аннотация: Цель двух докладов — представить систематический обзор классических и интуиционистских подходов к построению кондициональной (условной) логики, а также обсудить результаты, полученные в этой области.

В первой части будет дано введение в кондициональную логику как формальный аппарат для анализа рассуждений, использующих как индикативные, так и контрфактические условные выражения. Мы обсудим мотивацию введения кондициональных операторов и отличие их от условных выражений, формализуемых в других неклассических логиках. Будут рассмотрены ключевые системы, предложенные в работах Р. Сталнакера [8], Д. Льюиса [3, 4], Б. Челласа [1] и Д. Ньюта [5], их аксиоматические исчисления, различные типы семантик: семантика сфер, (обобщенная) реляционная семантика, семантика сравнительной возможности и селективно-функциональная семантика [5, 7, 9], — а также доказательства ряда метатеорем.

Во второй части акцент будет сделан на интуиционистских и конструктивных вариантах систем кондициональной логики, развивающихся в последние годы. Будут рассмотрены мотивации отказа от классических презумпций и постановка задачи о формализации контрфактических рассуждений в рамках конструктивного контекста. Подробно будут проанализированы работы Й. Вайса [11, 12], И. Чиарделли, С. Лью [2] и Г.К. Ольховикова [6], посвящённые как семантическим моделям (в частности, модифицированным реляционным семантикам — биреляционным моделям), так и системам аксиоматических исчислений для указанного типа логик. Отдельно будут проанализированы особенности конструктивных кондициональных логик, развиваемых над логикой N4 Д. Нельсона [10] и логикой C, разработанной Х. Вансингом.

Заключительная часть выступлений посвящена собственным результатам автора, включающим построение аксиоматических и субординатных натуральных исчислений для интуиционистских аналогов систем Сталнакера–Льюиса, конструктивной кондициональной коннексивной логики CCCL Вансинга-Унтерхубера [10] с аксимой сериальности, а также введение новых ограничений на кондициональное отношение достижимости в контексте кондициональных биреляционных шкал реляционной семантики. Эти результаты открывают перспективу дальнейшего развития интуиционистской (шире — конструктивной) кондициональной логики.

Литература:

[1] Chellas B.F. Basic Conditional Logic // Journal of Philosophical Logic. 1975. Vol. 5. No. 2. P. 133–153.
[2] Ciardelli I., Liu X. Intuitionistic Conditional Logics // Journal of Philosophical Logic. 2020. Vol. 49. No. 4. P. 807–832.
[3] Lewis D. Counterfactuals and Comparative Possibility // Journal of Philosophical Logic. 1973. Vol. 2. No. 4. P. 418–446.
[4] Lewis D. Counterfactuals. Oxford: Blackwell Publishing, 1973.
[5] Nute D., Cross C.B. Conditional Logic // Handbook of Philosophical Logic. Vol. 4. 2nd Edn. / Ed. by D.M. Gabbay, F. Guenthner. Dordrecht: Springer, 2002. P. 1–98.
[6] Olkhovikov G.K. An Intuitionistically Complete System of Basic Intuitionistic Conditional Logic // Journal of Philosophical Logic. 2024. Vol. 53. No. 5. P. 1199–1240.
[7] Segerberg K. Notes on Conditional Logic // Studia Logica. 1989. Vol. 48. No. 2. P. 157–168.
[8] Stalnaker R.C., Thomason R.H. A Seman

tic Analysis of Conditional Logic // Theoria. 1970. Vol. 36. No. 1. P. 23–42.
[9] Unterhuber M. Possible Worlds Semantics for Indicative and Counterfactual Conditionals? A Formal-Philosophical Inquiry into Chellas-Segerberg Semantics. Frankfurt: Ontos Verlag, 2013.
[10] Wansing H., Unterhuber M. Connexive Conditional Logic. Part 1 // Logic and Logical Philosophy. 2019. Vol. 28. P. 567– 610.
[11] Weiss Y. Basic Intuitionistic Conditional Logic // Journal of Philosophical Logic. 2018. Vol. 48. No. 3. P. 447–469.
[12] Weiss Y. Frontiers of Conditional Logic. PhD Thesis. New York: The City University of New York, 2019.
_________________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1085879818.html

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

В рамках логического семинара лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ) пройдет предзащита докторской диссертации Станислава Кикотя.

Среда, 24 сентября, 13:50 (время необычное!).

Предзащита будет онлайн, и мы устроим трансляцию по адресу
МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

Но это будет именно трансляция, докладчик будет онлайн.
Так что можно подключиться независимо. Для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Название диссертации: Исследование формальных систем, связанных с модальной логикой и базами данных.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в онлайн формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 213 (ул. Усачева, д. 6)
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

Дата и время: 26.09.2025 в 16:20

Докладчик: С.О. Сперанский (МИАН)

Название: Открытие алгоритмической неразрешимости

Аннотация:

Формализация понятия вычислимой функции и появление естественных примеров алгоритмически неразрешимых проблем — яркие события в истории современной математики и информатики, связанные с пионерскими работами Алана Тьюринга. Данная лекция будет посвящена стоящему за этими событиями математическому аппарату и его применениям. В частности, будет приведена схема доказательства неразрешимости небезызвестной «проблемы остановки». Кроме того, мы бегло обсудим классификацию математических проблем по степени их неразрешимости.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Семинар отдела математической логики (https://www.mathnet.ru/conf876, совместно с семинаром С.И. Адяна), очный доклад

Время: 29 сентября (понедельник), начало — в 16:00
Место: МИАН, ауд. 313 + Контур.Толк

А.А. Гайфуллин (МИАН, https://www.mathnet.ru/person/13368)

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

Аннотация:

В группе автоморфизмов свободной группы $F_n$ имеется важная подгруппа $IA_n$, состоящая из всех автоморфизмов, действующих тривиально на абелизации группы $F_n$; аналогичная подгруппа $IO_n$ есть в группе внешних автоморфизмов свободной группы. Изучение групп $IA_n$ и $IO_n$ восходит к классическим работам Нильсена и Магнуса. В частности, Магнус (1935) показал, что группа $IA_n$ конечно порождена и предъявил явно её порождающие.

Начиная с работы Андреадакиса (1965), в центре внимания ряда исследований оказался коммутант $[IA_n, IA_n]$. Естественный вопрос: являются ли группы $[IA_n, IA_n]$ и группы $[IO_n, IO_n]$ конечно порожденными при n2? (При n=2, согласно классическому результату Нильсена, все $IA$-автоморфизмы свободной группы $F_2$ внутренние; поэтому $[IA_2, IA_2]$ — бесконечно порожденная свободная группа.) В 2017 году М. Ершов и Хи доказали, что группы $[IA_n, IA_n]$ и, следовательно, группы $[IO_n, IO_n]$ конечно порождены при n3. Случай n=3 остаётся полностью открытым, и в этом случае имеется ряд доводов в пользу скорее отрицательного ответа на вопрос о конечной порожденности группы $[IA_3, IA_3]$ и даже её абелизации. Тем не менее, в докладе будет рассказано о недавнем результате докладчика, утверждающем, что в случае внешних автоморфизмов абелизация группы $[IO_3, IO_3]$ конечно порождена. Также будет получен аналогичный результат для группы классов отображений ориентируемой поверхности. Ключевую роль в доказательстве играет некоторое достаточное условие того, что конечно порожденный модуль над кольцом многочленов Лорана конечно порождён как абелева группа.

[ Планируется серия из двух докладов. ]

➰ ВК

#матлог #наука #спецсеминар

At 29 september we DON'T have Kolmogorov seminar meeting.
But at 19:00 Moscow time (30 min later that usual seminar time) Yury Kudryashov will give a talk "What is Lean and how does it help LLMs solve mathematics?" Yury works for Harmonic, one of the companies that managed to "solve" (in some sense) 5 out of 6 problems of International Math Olympiad this year using their LLM and other tools.

Abstract.

In the past few years, LLMs went from generating text that only look reasonable to generating correct solutions to IMO problems and, in some cases, research problems.
On the other hand, in many cases LLMs still prefer to hallucinate rather than admit failure.
How one can trust LLM-produced proofs? One of the answers to this question is to make an LLM produce a proof that can be formally verified by a computer.

In my talk, I will discuss the following questions:
- What is Lean? How do definitions, theorem statements, and proofs look like?
- How does it help LLMs solve math problems?
- What other tools can an LLM use?
- Can an LLM learn a new skill based on a limited amount of information?

A free discussion is planned after the talk, so please think about your questions/requests for comments (including examples/demonstrations/WTF experiences etc.)

Another request:

The possible application of AI in math are obviously a hot topic. The Mathematical Intelligencer is trying to collect people's observations about their personal experiences (the quotes may be published); just a few lines about these questions (some of them) would be great.

Questions:
1) What was yours most impressive ``success story'' of using AI, LLM and related tools for mathematics research/teaching?
2) What was yours most disappointing experience of this kind?
3) What would you expect to happen, say, 5 years from now in this regard?
Please send your answers to sasha.shen@gmail.com.

For receive the zoom link, please email sasha.shen@gmail.com.

➰ ВК

#матлог #учёба #спецкурс

В.Е.Плиско прочитает спецкурс «Метод резолюций». Это полугодовой спецкурс по выбору кафедры.

Первая лекция: 3 октября

Место проведения: 425 аудитория, 2 ГУМ

Время проведения: пятница 18:30–20:05

Аннотация.
В спецкурсе детально излагается так называемый метод резолюций, используемый при построении систем автоматического доказательства теорем. Содержание: логика первого порядка; теорема Эрбрана; метод резолюций для логики высказываний; алгоритм унификации; метод резолюций для логики предикатов; уточнения исчисления резолюций; применения метода резолюций в математической логике. Предварительных знаний из области математической логики не требуется.

Литература:
В.Н.Крупский, В.Е.Плиско. Математическая логика и теория алгоритмов. М.: Академия, 2013. Глава 14.
Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
A.Leitsch. The Resolution Calculus. Springer, 1997.

➰ ВК

#матлог #спецсеминар #не_мехмат

Семинар Добрушинской лаборатории Высшей школы современной математики МФТИ (ВШМ).
30 сентября, вторник, 16:15, Адм. корпус ауд.322.
www.mathnet.ru/conf167

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный + трансляция в телемосте
Если у вас нет пропуска МФТИ, то на входе сообщайте, что идете на семинар и не забудьте паспорт.

Докладчик: Денис Савельев (МФТИ):
Называние: "Об отношениях на ультрафильтрах, лежащих между предпорядками Рудин–Кейслера и Комфорта, часть I.
// On relations on ultrafilters lying between the Rudin–Keisler and Comfort preorders, part I."

Аннотация.
В 2010 г. докладчиком был предложен канонический способ расширения алгебраической системы (т.е. множества с произвольными конечноместными операциями и отношениями на нём) ультрафильтрами, обобщающий компактификацию Чеха–Стоуна дискретного пространства. При рассмотрении таких расширений многоместных операций естественно возникают отношения на ультрафильтрах, обобщающие классический предпорядок Рудин–Кейслера (который задается одноместными операциями). Оказывается, что возрастающую цепь этих отношений можно продолжить трансфинитно, причём возникающие отношения будут соответствовать определённым непрерывным бесконечноместным операциям, которые тоже допускают расширения ультрафильтрами. Более того, объединение всех полученных отношений даёт другое хорошо известное отношение на ультрафильтрах — предпорядок Комфорта. Будет показано, как вычисляется композиция этих отношений; как следствие, будет установлен критерий того, когда отношение является предпорядком.

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

Доклад основан на совместной работе с Н.Л.Поляковым (ВШЭ).

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
1 октября (среда) в 18:10 состоится заседание научно-исследовательского семинара «From the Logical Point of View»

Тема доклада: Классические и интуиционистские кондициональные логики: метатеория, семантика, теория доказательств​​ (часть 2)

Докладчик: Игорь Зайцев (стажер-исследователь МЛ ЛогЛинФФ)

Аннотация:
Цель двух докладов — представить систематический обзор классических и интуиционистских подходов к построению кондициональной (условной) логики, а также обсудить результаты, полученные в этой области.

В первой части будет дано введение в кондициональную логику как формальный аппарат для анализа рассуждений, использующих как индикативные, так и контрфактические условные выражения. Мы обсудим мотивацию введения кондициональных операторов и отличие их от условных выражений, формализуемых в других неклассических логиках. Будут рассмотрены ключевые системы, предложенные в работах Р. Сталнакера [8], Д. Льюиса [3, 4], Б. Челласа [1] и Д. Ньюта [5], их аксиоматические исчисления, различные типы семантик: семантика сфер, (обобщенная) реляционная семантика, семантика сравнительной возможности и селективно-функциональная семантика [5, 7, 9], — а также доказательства ряда метатеорем.

Во второй части акцент будет сделан на интуиционистских и конструктивных вариантах систем кондициональной логики, развивающихся в последние годы. Будут рассмотрены мотивации отказа от классических презумпций и постановка задачи о формализации контрфактических рассуждений в рамках конструктивного контекста. Подробно будут проанализированы работы Й. Вайса [11, 12], И. Чиарделли, С. Лью [2] и Г.К. Ольховикова [6], посвящённые как семантическим моделям (в частности, модифицированным реляционным семантикам — биреляционным моделям), так и системам аксиоматических исчислений для указанного типа логик. Отдельно будут проанализированы особенности конструктивных кондициональных логик, развиваемых над логикой N4 Д. Нельсона [10] и логикой C, разработанной Х. Вансингом.

Заключительная часть выступлений посвящена собственным результатам автора, включающим построение аксиоматических и субординатных натуральных исчислений для интуиционистских аналогов систем Сталнакера–Льюиса, конструктивной кондициональной коннексивной логики CCCL Вансинга-Унтерхубера [10] с аксимой сериальности, а также введение новых ограничений на кондициональное отношение достижимости в контексте кондициональных биреляционных шкал реляционной семантики. Эти результаты открывают перспективу дальнейшего развития интуиционистской (шире — конструктивной) кондициональной логики.

Литература:
[1] Chellas B.F. Basic Conditional Logic // Journal of Philosophical Logic. 1975. Vol. 5. No. 2. P. 133–153.
[2] Ciardelli I., Liu X. Intuitionistic Conditional Logics // Journal of Philosophical Logic. 2020. Vol. 49. No. 4. P. 807–832.
[3] Lewis D. Counterfactuals and Comparative Possibility // Journal of Philosophical Logic. 1973. Vol. 2. No. 4. P. 418–446.
[4] Lewis D. Counterfactuals. Oxford: Blackwell Publishing, 1973.
[5] Nute D., Cross C.B. Conditional Logic // Handbook of Philosophical Logic. Vol. 4. 2nd Edn. / Ed. by D.M. Gabbay, F. Guenthner. Dordrecht: Springer, 2002. P. 1–98.
[6] Olkhovikov G.K. An Intuitionistically Complete System of Basic Intuitionistic Conditional Logic // Journal of Philosophical Logic. 2024. Vol. 53. No. 5. P.

1199–1240.
[7] Segerberg K. Notes on Conditional Logic // Studia Logica. 1989. Vol. 48. No. 2. P. 157–168.
[8] Stalnaker R.C., Thomason R.H. A Semantic Analysis of Conditional Logic // Theoria. 1970. Vol. 36. No. 1. P. 23–42.
[9] Unterhuber M. Possible Worlds Semantics for Indicative and Counterfactual Conditionals? A Formal-Philosophical Inquiry into Chellas-Segerberg Semantics. Frankfurt: Ontos Verlag, 2013.
[10] Wansing H., Unterhuber M. Connexive Conditional Logic. Part 1 // Logic and Logical Philosophy. 2019. Vol. 28. P. 567– 610.
[11] Weiss Y. Basic Intuitionistic Conditional Logic // Journal of Philosophical Logic. 2018. Vol. 48. No. 3. P. 447–469.
[12] Weiss Y. Frontiers of Conditional Logic. PhD Thesis. New York: The City University of New York, 2019.
_________________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1085879818.html

➰ ВК

#матлог #учёба #просеминар

💥В среду 1 октября состоится очередное занятие просеминара по математической логике и информатике.

✨Тема: "Аксиоматическая теория множеств" (А.А.Оноприенко).
✨Аннотация. В основе современной теории множеств лежат аксиомы, предложенные Цермело и Френкелем. На просеминаре мы детально рассмотрим эти аксиомы.
✨Можно заранее порешать задачи (прикреплены к посту).

✅Просеминар проходит по средам в 15:00-16:35 в аудитории 406 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале по хештегу #просеминар ‼

📝 set2025.pdf

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
4 октября (суббота) в 18:00 (GMT+3) состоится заседание научно-учебного семинара «Математическая логика и теория категорий» (online).

Тема доклада: Actual Causality: A Survey.

Докладчик: Joseph Y. Halpern (Joseph C. Ford Professor in the Computer Science Department at Cornell University).

Аннотация: What does it mean that an event C "actually caused'' event E? The problem of defining actual causation goes beyond mere philosophical speculation.

For example, in many legal arguments, it is precisely what needs to be established in order to determine responsibility. (What exactly was the actual cause of the car accident or the medical problem?) The philosophy literature has been struggling with the problem of defining causality since the days of Hume, in the 1700s. Many of the definitions have been couched in terms of counterfactuals. (C is a cause of E if, had C not happened, then E would not have happened.) In 2001, Judea Pearl and I introduced a new definition of actual cause, using Pearl's notion of structural equations to model counterfactuals. The definition has been revised twice since then, extended to deal with notions like "responsibility" and "blame", and applied in databases and program verification. I survey the last 15 years of work here, including joint work with Judea Pearl, Hana Chockler, and Chris Hitchcock. The talk will be completely self-contained.
_________________________

Ждём вас в кабинете А-117 или в Zoom!

Анонс и регистрация: https://llfp.hse.ru/announcements/1087904123.html

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/).

Время: 2 октября (четверг), начало — в 16:00
Место: МИАН, ком. 530 + Контур.Толк

К.А. Ковалёв (МИАН), Л.В. Дворкин (МГУ)

О (не)разрешимости первопорядковых теорий метрических, векторных и гильбертовых пространств

Краткая аннотация доклада:

Будет показано, что для теорий нормированных и банаховых пространств справедлива нижняя оценка \Pi^2_1, т.е. соответствующие теории являются \Pi^2_1-трудными. Также будет показано, что теории гильбертовых и евклидовых пространств сводятся к теории вещественно замкнутых полей и, следовательно, разрешимы.

[ Доклад сделает К.А. Ковалёв. ]

Общая аннотация серии:

В рамках четырёх запланированных заседаний семинара мы намерены детально изучить работу

R.M. Solovay, R.D. Arthan, J. Harrison. Some new results on decidability for elementary algebra and geometry. Annals of Pure and Applied Logic 163(12), 1765–1802, 2012.
https://doi.org/10.1016/j.apal.2012.04.003

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

Оказывается, что проверку выполнимости первопорядковых формул в векторных, предгильбертовых и гильбертовых пространствах можно свести к проверке выполнимости в поле вещественных чисел. Последняя, как известно, разрешима в силу теоремы Зайденберга–Тарского.

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

Мы планируем рассмотреть доказательства упомянутых результатов. Предполагается, что слушатели обладают базовыми знаниями о первопорядковых теориях и их моделях.

Если планируете посетить заседание (очно или онлайн через Контур.Толк), пожалуйста, зарегистрируйтесь по ссылке в верхней части страницы семинара:
https://www.mathnet.ru/conf2533

➰ ВК

#матлог #учёба #спецкурс

В следующий вторник 7 октября в ауд. 1408 Главного здания МГУ начнётся полугодовой спецкурс Н.К. Верещагина "Односторонние функции и их применения".

Лекции будут по вторникам на пятой паре 16:45-18:20 на мехмате МГУ, аудитория 1408.

❗Ранее в группе было объявление про этот спецкурс, но во времени проведения была ошибка! Поэтому публикуем объявление повторно, дополнив его информацией о спецкурсе.

Аннотация.
По определению одностороннюю функцию легко вычислить, но обратную к ней вычислить трудно. Односторонние функции используются при построении генераторов случайных чисел, схем шифрования, протоколов электронной подписи и др.

Программа.
Односторонние функции (сильно и слабо). Теорема Левина - Гольдрайха о преобразовании слабо односторонней функции в сильно одностороннюю. Обобщение понятия односторонней функции —- частичные односторонние функции (с равномерным распределением). Односторонние перестановки. Функция Рабина, функция RSA, дискретная экспонента.
Статистически и вычислительно неотличимые случайные величины. Свойства вычислительно неотличимых случайных величин. Полиномиально генерируемые и доступные последовательности случайных величин. Генераторы псевдослучайных чисел (ПСЧ). Слабая необратимость генераторов ПСЧ.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом. Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки.
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ. Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.

Список источников
Введение в криптографию. Под общей редакцией В.В.Ященко. —- 3-е изд. доп. —- М.: МЦНМО: "ЧеРо", 2000. —- 288 с.
М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко. Криптография в банковском деле. М.: МИФИ, 1997.
O. Goldreich. Foundations of cryptography. Basic tools. Cambridge Univ. Press. 2001. 400 p.
O. Goldreich. Foundations of cryptography. Basic applications. Cambridge Univ. Press. 2004

➰ ВК

#матлог #учёба #спецсеминар

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425.

3 октября 2025 г.

Г. Г. Черевиченко
"Малоизвестные формализации логики высказываний"

Предполагается рассмотреть таблицы Бета и диалоги Лоренцена. Хочется иметь исчисление, в котором удобно искать вывод формулы "снизу вверх", причём получаться должен или вывод, или контрмодель (Крипке, если логика интуиционистская). Такие исчисления есть.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

6 October, 18:30 MSK

Arturo Merino (Universidad de O'Higgin, https://amerino.cl/).

0,1-polyhedra.

A 0-1 polyhedron is a polyhedron whose vertices are 0,1 vectors. For example, for a given graph G, one can define a 0,1-polyhedron whose vertices are matchings of G.
There is a classical result that any 0,1-polyhedron admits a Hamiltonian path along its edges. The idea is to first try to understand this result, and then discuss what is known about efficient generation of the vertices of 0,1-polyhedra.

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 109 (ул. Усачева, д. 6). Мы надеемся, что получится транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.

Дата и время: 03.10.2025 (пятница) в 16:20

Докладчик: Анастасия Оноприенко

Название: Интуиционистская логика

Аннотация:
На рубеже XIX-XX веков в существующей на тот момент теории множеств было обнаружено большое число парадоксов.
Так как теория множеств мыслилась как попытка формализовать всю имеющуюся математику, это привело к кризису оснований математики.
Брауэр видел в качестве возможного варианта разрешения этой проблемы пересмотр смысла логических связок и кванторов и отказ от рассмотрения абстрактных объектов, существующих лишь в нашей, порой противоречивой, фантазии.
В докладе будет определена интуиционистская логика, рассмотрена её семантика Крипке, некоторые следствия из теоремы о полноте (не конечнозначность интуиционистской логики, теорема Гливенко), а также перевод интуиционистской логики высказываний в модальную логику S4.
В конце будет сделан краткий обзор некоторых более свежих результатов и открытых вопросов в этой области.

➰ ВК