#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 30.01.2026 в 16:20
Докладчик: Анна Оверчук
Название: Модели вычисления и их сложность. Классические, вероятностные, квантовые.
Аннотация:
Хорошо известна одна из проблем тысячелетия: вопрос о равенстве классов сложности P и NP.
По своей сути, эта проблема, как и многие другие в теории сложности, упирается в сравнение различных математических моделей (концепций) вычислений. На практике оказывается крайне сложно установить строгие соотношения между принципиально разными вычислительными подходами.
В своем докладе я сосредоточусь на сравнении трёх ключевых моделей: классической(машина Тьюринга), вероятностной и квантовой.
Я расскажу о способах их формального определения, обсужу, как их расширяют вероятностные и квантовые подходы, и как сравнивать их вычислительную мощность между собой.
➰ ВК
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 30.01.2026 в 16:20
Докладчик: Анна Оверчук
Название: Модели вычисления и их сложность. Классические, вероятностные, квантовые.
Аннотация:
Хорошо известна одна из проблем тысячелетия: вопрос о равенстве классов сложности P и NP.
По своей сути, эта проблема, как и многие другие в теории сложности, упирается в сравнение различных математических моделей (концепций) вычислений. На практике оказывается крайне сложно установить строгие соотношения между принципиально разными вычислительными подходами.
В своем докладе я сосредоточусь на сравнении трёх ключевых моделей: классической(машина Тьюринга), вероятностной и квантовой.
Я расскажу о способах их формального определения, обсужу, как их расширяют вероятностные и квантовые подходы, и как сравнивать их вычислительную мощность между собой.
➰ ВК
VK
Кафедра математической логики МГУ. Пост со стены.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
❤1
#матлог #учёба #спецсеминар
"Семинар по геометрической теории групп" в Математическом институте им. В.А. Стеклова РАН (Москва, ул. Губкина, 8) под руководством И.Г. Лысёнка и А.Л. Таламбуцы начинает работу в весеннем семестре.
Первое заседание: 12 февраля
Место проведения: МИАН, ком. 430
Время проведения: четверг 16:00
Страница семинара: https://www.mathnet.ru/conf1892
‼Всем участникам (в т.ч. онлайн-участникам) просьба зарегистрироваться на странице семинара по ссылке выше. Будет возможность удалённого подключения через Контур Толк (ссылку получат зарегистрированные слушатели).
Основная цель семинара — обзор и изложение интересных результатов в области геометрической теории групп и смежных областях. Доклады будут готовиться на основе опубликованных статей разных авторов, а также на основе работ участников семинара и приглашённых докладчиков.
От участников не требуется специальной подготовки. Основное требование — наличие интереса к получению новых математических знаний. Участие студентов категорически приветствуется (предполагается зачёт).
Расписание докладов формируется в процессе работы семинара. Предварительно запланировано три студенческих доклада.
➰ ВК
"Семинар по геометрической теории групп" в Математическом институте им. В.А. Стеклова РАН (Москва, ул. Губкина, 8) под руководством И.Г. Лысёнка и А.Л. Таламбуцы начинает работу в весеннем семестре.
Первое заседание: 12 февраля
Место проведения: МИАН, ком. 430
Время проведения: четверг 16:00
Страница семинара: https://www.mathnet.ru/conf1892
‼Всем участникам (в т.ч. онлайн-участникам) просьба зарегистрироваться на странице семинара по ссылке выше. Будет возможность удалённого подключения через Контур Толк (ссылку получат зарегистрированные слушатели).
Основная цель семинара — обзор и изложение интересных результатов в области геометрической теории групп и смежных областях. Доклады будут готовиться на основе опубликованных статей разных авторов, а также на основе работ участников семинара и приглашённых докладчиков.
От участников не требуется специальной подготовки. Основное требование — наличие интереса к получению новых математических знаний. Участие студентов категорически приветствуется (предполагается зачёт).
Расписание докладов формируется в процессе работы семинара. Предварительно запланировано три студенческих доклада.
➰ ВК
#матлог #конференции
Сегодня начинается регистрация на международную научную конференцию студентов, аспирантов и молодых учёных «Ломоносов-2026» (https://lomonosov-msu.ru/rus/event/10500/). В этом году конференция пройдет с 10 по 25 апреля.
Регистрация продлится до 2 марта (включительно).
По решению центрального оргкомитета формат конференции - очный. Однако для докладчиков из других регионов и стран возможно онлайн-подключение к заседаниям подсекций.
На секции «Математика и механика» будут представлены следующие подсекции.
👉Аэромеханика
👉Вещественный, комплексный и функциональный анализ
👉Вычислительная математика, математическое моделирование и численные методы
👉Вычислительная механика
👉Газовая и волновая динамика
👉Геометрия и топология
👉Гидромеханика
👉Дискретная математика и математическая кибернетика
👉Дифференциальные уравнения, динамические системы и оптимальное управление
👉Математическая логика, алгебра и теория чисел
👉Механика композитов
👉Прикладная механика и управление
👉Теоретическая механика и мехатроника
👉Теория вероятностей и математическая статистика
👉Теория и методика преподавания математики
👉Теория пластичности
👉Теория упругости
👉Абитуриенты (станет доступна в ближайшее время)
Вместе с заявкой участник также должен прикрепить тезисы своего выступления. Правила оформления тезисов Вы можете найти по ссылке: https://lomonosov-msu.ru/rus/event/10500/page/5067. Наличие тезисов - необходимое условие допуска к участию.
➰ ВК
Сегодня начинается регистрация на международную научную конференцию студентов, аспирантов и молодых учёных «Ломоносов-2026» (https://lomonosov-msu.ru/rus/event/10500/). В этом году конференция пройдет с 10 по 25 апреля.
Регистрация продлится до 2 марта (включительно).
По решению центрального оргкомитета формат конференции - очный. Однако для докладчиков из других регионов и стран возможно онлайн-подключение к заседаниям подсекций.
На секции «Математика и механика» будут представлены следующие подсекции.
👉Аэромеханика
👉Вещественный, комплексный и функциональный анализ
👉Вычислительная математика, математическое моделирование и численные методы
👉Вычислительная механика
👉Газовая и волновая динамика
👉Геометрия и топология
👉Гидромеханика
👉Дискретная математика и математическая кибернетика
👉Дифференциальные уравнения, динамические системы и оптимальное управление
👉Математическая логика, алгебра и теория чисел
👉Механика композитов
👉Прикладная механика и управление
👉Теоретическая механика и мехатроника
👉Теория вероятностей и математическая статистика
👉Теория и методика преподавания математики
👉Теория пластичности
👉Теория упругости
👉Абитуриенты (станет доступна в ближайшее время)
Вместе с заявкой участник также должен прикрепить тезисы своего выступления. Правила оформления тезисов Вы можете найти по ссылке: https://lomonosov-msu.ru/rus/event/10500/page/5067. Наличие тезисов - необходимое условие допуска к участию.
➰ ВК
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 4 февраля в 14:00.
Место проведения:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Введение в семантику первопорядковых модальных логик - часть 5
Докладчик: В.Б. Шехтман
Доклад основан на вводных лекциях о семантике первопорядковых модальных логик, прочитанных совместно с Д. Шкатовым летом 2025 года в рамках ESSLLI 2025. Будут изложены результаты о полноте относительно шкал и пучков Крипке - сохранение полноты при операции Boxing, а также метод селективных игр.
Необходимые сведения из частей 1-4 будут даны в начале доклада.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 4 февраля в 14:00.
Место проведения:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Введение в семантику первопорядковых модальных логик - часть 5
Докладчик: В.Б. Шехтман
Доклад основан на вводных лекциях о семантике первопорядковых модальных логик, прочитанных совместно с Д. Шкатовым летом 2025 года в рамках ESSLLI 2025. Будут изложены результаты о полноте относительно шкал и пучков Крипке - сохранение полноты при операции Boxing, а также метод селективных игр.
Необходимые сведения из частей 1-4 будут даны в начале доклада.
➰ ВК
#матлог
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
4 февраля в 18:10 состоится 110-е заседание научно-теоретического семинара «Формальная философия».
Тема доклада: Когда и как принимается логика: эпистемология "adoption problem".
Докладчик: Александр Хлебалин (старший научный сотрудник Институт философии и права СО РАН, к.филос.н.).
Аннотация: «Проблема принятия», или «adoption problem» обозначает дискуссию, развернувшуюся вокруг лекции Сола А. Крипке (1975 г.), представленной позже (2024 г.) как статьи «The Question of Logic», поводом для которой стала работа Х. Патнэма «Is Logic Empirical?» (1968). Это обмен мнения сконцентрирован на вопросе о возможности рациональной смены используемой логики. Как сами инициаторы дискуссии, так и вступившие в нее участники, при обсуждении исходной проблемы конкретизировали и, одновременно, расширили исходную формулировку до трех основных составляющих проблемы:
(1) Какова природа аргументов в пользу допустимости рационального изменения используемой логики?
(2) Как может ответить на проблему принятия тот, кто считает, что рациональное принятие логики возможно?
(3) Каковы последствия возможных решений проблемы для классических вопросов философии логики, таких как вопрос о природе нормативности логики, эпистемологического статуса логической истины и т.п.?
Доклад посвящен экспозиции возникновения и развития «проблема принятия» в философии логики, освещению сформулированных подходов к ее решению, следствий принятия позиций для смежных классических проблем эпистемологии логики.
Литература:
1. Putnam H. IS LOGIC EMPIRICAL?// Boston Studies in the Philosophy of Science. V.
2. Kripke S. The Question of Logic.// Mind, Vol. 133 . 529.
3. Birman R. The Adoption Problem and the Epistemology of Logic // Mind, Vol. 133 . 529 .
_____________________
Ждём вас в кабинете А-117 или в Zoom!
Анонс и регистрация: https://llfp.hse.ru/announcements/1123629624.html
➰ ВК
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
4 февраля в 18:10 состоится 110-е заседание научно-теоретического семинара «Формальная философия».
Тема доклада: Когда и как принимается логика: эпистемология "adoption problem".
Докладчик: Александр Хлебалин (старший научный сотрудник Институт философии и права СО РАН, к.филос.н.).
Аннотация: «Проблема принятия», или «adoption problem» обозначает дискуссию, развернувшуюся вокруг лекции Сола А. Крипке (1975 г.), представленной позже (2024 г.) как статьи «The Question of Logic», поводом для которой стала работа Х. Патнэма «Is Logic Empirical?» (1968). Это обмен мнения сконцентрирован на вопросе о возможности рациональной смены используемой логики. Как сами инициаторы дискуссии, так и вступившие в нее участники, при обсуждении исходной проблемы конкретизировали и, одновременно, расширили исходную формулировку до трех основных составляющих проблемы:
(1) Какова природа аргументов в пользу допустимости рационального изменения используемой логики?
(2) Как может ответить на проблему принятия тот, кто считает, что рациональное принятие логики возможно?
(3) Каковы последствия возможных решений проблемы для классических вопросов философии логики, таких как вопрос о природе нормативности логики, эпистемологического статуса логической истины и т.п.?
Доклад посвящен экспозиции возникновения и развития «проблема принятия» в философии логики, освещению сформулированных подходов к ее решению, следствий принятия позиций для смежных классических проблем эпистемологии логики.
Литература:
1. Putnam H. IS LOGIC EMPIRICAL?// Boston Studies in the Philosophy of Science. V.
2. Kripke S. The Question of Logic.// Mind, Vol. 133 . 529.
3. Birman R. The Adoption Problem and the Epistemology of Logic // Mind, Vol. 133 . 529 .
_____________________
Ждём вас в кабинете А-117 или в Zoom!
Анонс и регистрация: https://llfp.hse.ru/announcements/1123629624.html
➰ ВК
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Logic Online Seminar (https://www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
09.02.2026, Т.Л. Яворская (МГУ): О семантике логики свидетельств первого порядка со связывающими модальностями (очный)
Доклад посвящен семантике гибридной логики первого порядка, в языке которой присутствуют и свидетельские термы, и модальность. Особенность таких логик в том, что язык позволяет выразить как утверждение "t является свидетельством формулы F, содержащей свободную переменную x", так и "для данного значения x, t является свидетельством формулы F(x)". В первом утверждении переменная x связанная, во втором свободная. Естественным представляется добавить в язык аналогичную конструкцию и для модальности (так называемые связывающие модальности). Мы определим логику, которая комбинирует логику свидетельств первого порядка FOLP и модальную логику S4 первого порядка со связывающими модальностями. Для этой логики определим модели в стиле моделей Фиттинга для FOLP, сформулируем теоремы о полноте и корректности относительно этой семантики и коротко обсудим основную идею доказательства. Мы используем эту семантику для доказательства невыводимости некоторых принципов и покажем, при каких требованиях мы можем гарантировать существование модели, отвечающей им.
➰ ВК
Logic Online Seminar (https://www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
09.02.2026, Т.Л. Яворская (МГУ): О семантике логики свидетельств первого порядка со связывающими модальностями (очный)
Доклад посвящен семантике гибридной логики первого порядка, в языке которой присутствуют и свидетельские термы, и модальность. Особенность таких логик в том, что язык позволяет выразить как утверждение "t является свидетельством формулы F, содержащей свободную переменную x", так и "для данного значения x, t является свидетельством формулы F(x)". В первом утверждении переменная x связанная, во втором свободная. Естественным представляется добавить в язык аналогичную конструкцию и для модальности (так называемые связывающие модальности). Мы определим логику, которая комбинирует логику свидетельств первого порядка FOLP и модальную логику S4 первого порядка со связывающими модальностями. Для этой логики определим модели в стиле моделей Фиттинга для FOLP, сформулируем теоремы о полноте и корректности относительно этой семантики и коротко обсудим основную идею доказательства. Мы используем эту семантику для доказательства невыводимости некоторых принципов и покажем, при каких требованиях мы можем гарантировать существование модели, отвечающей им.
➰ ВК
👍2
#матлог #учёба #спецсеминар
11 февраля 2026 г. состоится первое в 2026 г. заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН. Ранее семинар действовал под названием «Вероятностные и субструктурные логические системы».
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: https://www.mathnet.ru/conf2533
С.О. Сперанский (МИАН)
Об определимости в слабых арифметических структурах посредством монадических формул второго порядка
Аннотация:
Под слабой арифметической структурой мы будем понимать структуру на натуральных числах такую, что: а) все соответствующие ей предикаты и функции вычислимы; б) её элементарная (т.е. первопорядковая) теория разрешима. Примерами такого рода структур являются арифметики Пресбургера и Сколема, т.е. натуральные числа с равенством и сложением либо умножением. Цель настоящего доклада — познакомить слушателей с рядом результатов и проблем, связанных с определимостью в слабых арифметических структурах посредством монадических формул второго порядка. Здесь «монадические» означает, что все предикатные переменные имеют арность 1, т.е. их значениями являются одноместные предикаты на натуральных числах. На самом деле, в логике второго порядка именно монадические формулы зачастую представляют наибольший интерес. В докладе будет подробно разобран случай арифметики Пресбургера, менее подробно — случаи арифметики Сколема и некоторых родственных ей структур.
➰ ВК
11 февраля 2026 г. состоится первое в 2026 г. заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН. Ранее семинар действовал под названием «Вероятностные и субструктурные логические системы».
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: https://www.mathnet.ru/conf2533
С.О. Сперанский (МИАН)
Об определимости в слабых арифметических структурах посредством монадических формул второго порядка
Аннотация:
Под слабой арифметической структурой мы будем понимать структуру на натуральных числах такую, что: а) все соответствующие ей предикаты и функции вычислимы; б) её элементарная (т.е. первопорядковая) теория разрешима. Примерами такого рода структур являются арифметики Пресбургера и Сколема, т.е. натуральные числа с равенством и сложением либо умножением. Цель настоящего доклада — познакомить слушателей с рядом результатов и проблем, связанных с определимостью в слабых арифметических структурах посредством монадических формул второго порядка. Здесь «монадические» означает, что все предикатные переменные имеют арность 1, т.е. их значениями являются одноместные предикаты на натуральных числах. На самом деле, в логике второго порядка именно монадические формулы зачастую представляют наибольший интерес. В докладе будет подробно разобран случай арифметики Пресбургера, менее подробно — случаи арифметики Сколема и некоторых родственных ей структур.
➰ ВК
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 11 февраля в 14:15.
❗Время изменилось.
Место проведения:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Интуиционистская эпистемическая логика с точки зрения классической
Докладчик: Анастасия Оноприенко
Аннотация:
С. Артёмов и Т. Протопопеску построили три формальные системы, отражающие аспекты логики интуиционистского знания. Для таких логик основополагающим является принцип конструктивности знания, т.е. принцип корефлексии A→KA.
В 1933 году К. Гёдель описал вложение интуиционистского исчисления Int в классическую модальную логику S4, устроенное так: "добавить □ перед каждой подформулой". Т. Протопопеску рассматривает перевод интуиционистских эпистемических логик в расширения логики S4 с модальностями □ и V, устроенный как естественное продолжение перевода Гёделя: "навесить □ на каждую подформулу, а модальность K заменить на модальность V".
Существует более компактный вариант перевода Гёделя, в котором модальность □ навешивается только на атомарные формулы и на формулы вида A→B. В связи с этим можно рассматривать переводы, в которых формулы вида KA переводятся как VA (а не □VA). Для того, чтобы такой перевод являлся погружением логик, рассматриваются целевые логики с аксиомой VA→□VA.
В докладе мы рассмотрим погружения интуиционистских эпистемических логик IEL-, IEL, IEL+ в логики S4V−M, S4VM, S4V+M, а также погружение логики IEL+ в логику S4V+MU. Рассмотрим семантики Крипке этих логик. Установим конечность множества попарно неэквивалентных модальностей в логике S4V+MU и покажем, как отсюда следует финитная аппроксимируемость семантики Крипке этой логики.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 11 февраля в 14:15.
❗Время изменилось.
Место проведения:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Интуиционистская эпистемическая логика с точки зрения классической
Докладчик: Анастасия Оноприенко
Аннотация:
С. Артёмов и Т. Протопопеску построили три формальные системы, отражающие аспекты логики интуиционистского знания. Для таких логик основополагающим является принцип конструктивности знания, т.е. принцип корефлексии A→KA.
В 1933 году К. Гёдель описал вложение интуиционистского исчисления Int в классическую модальную логику S4, устроенное так: "добавить □ перед каждой подформулой". Т. Протопопеску рассматривает перевод интуиционистских эпистемических логик в расширения логики S4 с модальностями □ и V, устроенный как естественное продолжение перевода Гёделя: "навесить □ на каждую подформулу, а модальность K заменить на модальность V".
Существует более компактный вариант перевода Гёделя, в котором модальность □ навешивается только на атомарные формулы и на формулы вида A→B. В связи с этим можно рассматривать переводы, в которых формулы вида KA переводятся как VA (а не □VA). Для того, чтобы такой перевод являлся погружением логик, рассматриваются целевые логики с аксиомой VA→□VA.
В докладе мы рассмотрим погружения интуиционистских эпистемических логик IEL-, IEL, IEL+ в логики S4V−M, S4VM, S4V+M, а также погружение логики IEL+ в логику S4V+MU. Рассмотрим семантики Крипке этих логик. Установим конечность множества попарно неэквивалентных модальностей в логике S4V+MU и покажем, как отсюда следует финитная аппроксимируемость семантики Крипке этой логики.
➰ ВК
#матлог #учёба #спецкурс
Полугодовой спецкурс для 3-6 курсов, магистрантов и аспирантов
"Коммуникационная сложность" будет читаться проф. Н.К. Верещагиным по вторникам в 18:30-20:05 в ауд. 407 второго уч. корпуса.
Первая лекция — 17 февраля.
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может, поскольку у каждого из них недостаточно данных. Например, у одного из них имеется файл x, у другого файл y и нужно узнать, совпадают ли x и y. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание - в этом принципиальное отличие от теории сложности вычислений.
Предварительные знания: знакомство с линейной алгеброй в объеме одного семестра и с началами теории вероятностей.
Телеграмм канал: https://t.me/+9G993a4ym640ZTVi (там есть ссылка на подробную программу)
➰ ВК
Полугодовой спецкурс для 3-6 курсов, магистрантов и аспирантов
"Коммуникационная сложность" будет читаться проф. Н.К. Верещагиным по вторникам в 18:30-20:05 в ауд. 407 второго уч. корпуса.
Первая лекция — 17 февраля.
Простейшая модель в теории коммуникационной сложности такова. Имеются два участника (компьютера или человека), которые совместно хотят решить некоторую задачу. Ни один из них самостоятельно решить задачу не может, поскольку у каждого из них недостаточно данных. Например, у одного из них имеется файл x, у другого файл y и нужно узнать, совпадают ли x и y. Коммуникационная сложность измеряет минимально возможное количество битов, которым необходимо обменяться участникам, чтобы решить задачу. Время, необходимое для проведения локальных вычислений каждым из участников, не принимается во внимание - в этом принципиальное отличие от теории сложности вычислений.
Предварительные знания: знакомство с линейной алгеброй в объеме одного семестра и с началами теории вероятностей.
Телеграмм канал: https://t.me/+9G993a4ym640ZTVi (там есть ссылка на подробную программу)
➰ ВК
Telegram
Коммуникационная сложность
Nikolay Vereshchagin invites you to join this group on Telegram.
👍1
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Logic Online Seminar (https://www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
16.02.2026, D.I. Saveliev (MIPT): Solution to Hart–van Mill’s Problem 61 (onsite)
A natural question, appeared as Problem 61 in Hart and van Mill's list of open problems on βω (2024), asks whether every finite partial order is isomorphically embeddable in the Rudin--Keisler order on (types of) ultrafilters over a countable set. Although the positive answer, even for all countable partial orders, was obtained under CH in Blass' thesis (1970), the situation in ZFC alone has remained widely open. The solution was obtained by the speaker jointly with Poliakov (2025). We show that ZFC is sufficient not only to re-prove Blass' result but to prove a much stronger fact: the lattices of finite subsets of a set of cardinality 2^𝔠, and of countable subsets of a set of cardinality ℵ_1, both ordered by inclusion, are embeddable in ultrafilters with any relation lying between the Rudin--Keisler and Comfort orders.
K. P. Hart, J. van Mill, “Problems on βN”, Topology Appl., 364:1 (2025), 109092, 24 pp. arXiv:2205.11204.
N. L. Poliakov, D. I. Saveliev, “On embedding of partially ordered sets in (βω,⩽_RK)”, 2025, arXiv: 2511.19354.
N. L. Poliakov, D. I. Saveliev, “Solution to Hart–van Mill’s problem 61”, Russ. Math. Surv., 81:1 (487) (2026), 205–206 (to appear).
➰ ВК
Logic Online Seminar (https://www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
16.02.2026, D.I. Saveliev (MIPT): Solution to Hart–van Mill’s Problem 61 (onsite)
A natural question, appeared as Problem 61 in Hart and van Mill's list of open problems on βω (2024), asks whether every finite partial order is isomorphically embeddable in the Rudin--Keisler order on (types of) ultrafilters over a countable set. Although the positive answer, even for all countable partial orders, was obtained under CH in Blass' thesis (1970), the situation in ZFC alone has remained widely open. The solution was obtained by the speaker jointly with Poliakov (2025). We show that ZFC is sufficient not only to re-prove Blass' result but to prove a much stronger fact: the lattices of finite subsets of a set of cardinality 2^𝔠, and of countable subsets of a set of cardinality ℵ_1, both ordered by inclusion, are embeddable in ultrafilters with any relation lying between the Rudin--Keisler and Comfort orders.
K. P. Hart, J. van Mill, “Problems on βN”, Topology Appl., 364:1 (2025), 109092, 24 pp. arXiv:2205.11204.
N. L. Poliakov, D. I. Saveliev, “On embedding of partially ordered sets in (βω,⩽_RK)”, 2025, arXiv: 2511.19354.
N. L. Poliakov, D. I. Saveliev, “Solution to Hart–van Mill’s problem 61”, Russ. Math. Surv., 81:1 (487) (2026), 205–206 (to appear).
➰ ВК
#матлог #конференция
Научно-образовательный математический центр Приволжского федерального округа приглашает вас принять участие в VI Конференции математических центров России, которая пройдет с 17 по 22 августа 2026 года в г. Казани на базе Казанского (Приволжского) федерального университета.
К участию в конференции приглашаются представители российской и мировой математической общественности: аспиранты, студенты, сотрудники региональных математических центров и математических центров мирового уровня, научные и педагогические работники.
Формат работы конференции очный, будут представлены пленарные, секционные и постерные доклады по актуальным направлениям развития и современным достижениям математической науки.
В приложении - информационное письмо о проведении конференции.
Подробная информация о мероприятии находится на официальном сайте конференции: https://mathcenter.kpfu.ru/mc-conf
По всем возникающим вопросам следует обращаться на почту оргкомитета по адресу: mcVI-conf@yandex.ru
📝 Первое информационное сообщение.pdf
➰ ВК
Научно-образовательный математический центр Приволжского федерального округа приглашает вас принять участие в VI Конференции математических центров России, которая пройдет с 17 по 22 августа 2026 года в г. Казани на базе Казанского (Приволжского) федерального университета.
К участию в конференции приглашаются представители российской и мировой математической общественности: аспиранты, студенты, сотрудники региональных математических центров и математических центров мирового уровня, научные и педагогические работники.
Формат работы конференции очный, будут представлены пленарные, секционные и постерные доклады по актуальным направлениям развития и современным достижениям математической науки.
В приложении - информационное письмо о проведении конференции.
Подробная информация о мероприятии находится на официальном сайте конференции: https://mathcenter.kpfu.ru/mc-conf
По всем возникающим вопросам следует обращаться на почту оргкомитета по адресу: mcVI-conf@yandex.ru
📝 Первое информационное сообщение.pdf
➰ ВК
mathcenter.kpfu.ru
Конференция математических центров
VI Конференция математических центров России
👍1
#матлог #учёба #спецсеминар
18 февраля 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
С. Л. Кузнецов (МИАН)
Эффективная неотделимость и её применения для теорий с неподвижными точками
Аннотация:
Техника эффективной неотделимости позволяет доказывать теоремы об алгоритмической неразрешимости и $\Sigma^0_1$-полноте логических теорий в ситуациях, когда прямое сведение известных задач, таких как задача останова машины Тьюринга, построить не получается. Будет рассказано об эффективной неотделимости, приведена новая пара эффективно неотделимых множеств — нетотальных контекстно-свободных грамматик и так называемых регулярно тотальных контекстно-свободных грамматик. Далее с помощью этой пары будет доказана $\Sigma_0^1$-полнота эквациональных теорий алгебр Клини с делениями и алгебр Хомского — идемпотентных полуколец с оператором взятия наименьшей неподвижной точки.
Доклад частично основан на недавней совместной работе автора с А. Дасом и А. Де.
Доклад планируется на два заседания семинара.
➰ ВК
18 февраля 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
С. Л. Кузнецов (МИАН)
Эффективная неотделимость и её применения для теорий с неподвижными точками
Аннотация:
Техника эффективной неотделимости позволяет доказывать теоремы об алгоритмической неразрешимости и $\Sigma^0_1$-полноте логических теорий в ситуациях, когда прямое сведение известных задач, таких как задача останова машины Тьюринга, построить не получается. Будет рассказано об эффективной неотделимости, приведена новая пара эффективно неотделимых множеств — нетотальных контекстно-свободных грамматик и так называемых регулярно тотальных контекстно-свободных грамматик. Далее с помощью этой пары будет доказана $\Sigma_0^1$-полнота эквациональных теорий алгебр Клини с делениями и алгебр Хомского — идемпотентных полуколец с оператором взятия наименьшей неподвижной точки.
Доклад частично основан на недавней совместной работе автора с А. Дасом и А. Де.
Доклад планируется на два заседания семинара.
➰ ВК
👍1
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 20.02.2026 в 16:20
Язык доклада: английский.
Speaker: Sayantan Roy
Title: Abstract Model Structures and Compactness Theorems
Abstract: The compactness theorem for a logic states, roughly, that the satisfiability of a set of wffs can be determined from the satisfiability of its finite subsets, and vice versa. Usually, proofs of this theorem depend on the syntactic/semantic particularities of the corresponding logic. In this talk, using the notion of abstract model structures, we investigate a generalized notion of compactness that is independent of these. Thus, in terms of spirit, this work belongs to the subject known as abstract model theory although methodologically, it goes beyond it (e.g., we do not maintain the same commitment lack the strong commitment to the conventional concrete systems of logic that are characteristic features of works in this area). We also differ from a more categorical take to the subject since our approach is purely set-theoretic. We, however, do not compromise with the level of generality, and obtain several characterization theorems for a particular class of compact abstract model structures, generalizing the traditional Henkin-style, topological and ultrproduct proofs respectively. Finally, some open problems and directions for future research are discussed as well.
➰ ВК
Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.
Семинар пройдет в очном формате с одновременной трансляцией
на Математическом факультете ВШЭ, в аудитории 110 (ул. Усачева, д. 6). Мы будем транслировать доклад в zoom, но лучше приходите очно.
Если вам нужен пропуск в здание матфака, пришлите ваши ФИО и просьбу о пропуске на почту kudinov.andrey@gmail.com.
Дата и время: 20.02.2026 в 16:20
Язык доклада: английский.
Speaker: Sayantan Roy
Title: Abstract Model Structures and Compactness Theorems
Abstract: The compactness theorem for a logic states, roughly, that the satisfiability of a set of wffs can be determined from the satisfiability of its finite subsets, and vice versa. Usually, proofs of this theorem depend on the syntactic/semantic particularities of the corresponding logic. In this talk, using the notion of abstract model structures, we investigate a generalized notion of compactness that is independent of these. Thus, in terms of spirit, this work belongs to the subject known as abstract model theory although methodologically, it goes beyond it (e.g., we do not maintain the same commitment lack the strong commitment to the conventional concrete systems of logic that are characteristic features of works in this area). We also differ from a more categorical take to the subject since our approach is purely set-theoretic. We, however, do not compromise with the level of generality, and obtain several characterization theorems for a particular class of compact abstract model structures, generalizing the traditional Henkin-style, topological and ultrproduct proofs respectively. Finally, some open problems and directions for future research are discussed as well.
➰ ВК
VK
Кафедра математической логики МГУ. Пост со стены.
#матлог #учёба #семинар #не_мехмат #ВШЭ
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
Уважаемые коллеги, приглашаем вас принять участие в з... Смотрите полностью ВКонтакте.
👍1
#матлог #не_мехмат #ВШЭ
54-е заседание Математического семинара ФКН состоится 27 февраля в 18:10.
На семинаре выступит Андрей Кудинов с докладом "Модальная логика топологических пространств и битопологическое произведение".
Хорошо известно, что логика высказываний полна относительно булевых алгебр, а любая булева алгебра вкладывается в множество подмножеств некоторого множества (теорема Стоуна). С другой стороны на топологическое пространство можно смотреть как на булеву алгебру подмножеств с операцией взятия внутренности. Куратовский предложил эквивалентную аксиоматизацию топологический пространств через оператор взятия внутренности. Оказалось, что эти аксиомы дают в точности аксиоматизацию модальной логики S4. Модальная логика высказываний, получается добавлением оператора к языку булевых формул. При этом этот язык получается очень слабо выразительным, многие естественные свойства топологических пространств (плотность, аксиомы отделимости, компактность и т.д.) оказываются невыразимыми. Тем не менее, большим плюсом модальной логики S4 является ее разрешимость, которая отсутствует в логике предикатов, в которой можно выразить гораздо больше свойств топологических пространств.
Во второй части доклада я расскажу про различные способы, обогащения языка модальной логики, которые позволяют выражать больше свойств топологических пространств, оставаясь в рамках разрешимых исчислений.
В третьей части доклада я расскажу про конструкцию битопологического произведения, которая возникла в рамках развития топологических модальных логик многомерных структур. Результатом произведения двух топологических пространств является битопологическое пространство с горизонтальной и вертикальной топологиями. В горизонтальной топологии множество открыто, если все проекции горизонтальных сечений открыты. Аналогично для вертикальной топологии. Эта конструкция позволяет различить топологические пространства, которые были неразличимы в других языках. Я расскажу про результаты в этой области и открытые вопросы.
Семинар пройдет по адресу Покровский бульвар 11, аудитория R306.
Информация о семинаре и аннотация предстоящего доклада: https://cs.hse.ru/seminatfkn/
Регистрация: https://cs.hse.ru/big-data/polls/788384338.html
➰ ВК
54-е заседание Математического семинара ФКН состоится 27 февраля в 18:10.
На семинаре выступит Андрей Кудинов с докладом "Модальная логика топологических пространств и битопологическое произведение".
Хорошо известно, что логика высказываний полна относительно булевых алгебр, а любая булева алгебра вкладывается в множество подмножеств некоторого множества (теорема Стоуна). С другой стороны на топологическое пространство можно смотреть как на булеву алгебру подмножеств с операцией взятия внутренности. Куратовский предложил эквивалентную аксиоматизацию топологический пространств через оператор взятия внутренности. Оказалось, что эти аксиомы дают в точности аксиоматизацию модальной логики S4. Модальная логика высказываний, получается добавлением оператора к языку булевых формул. При этом этот язык получается очень слабо выразительным, многие естественные свойства топологических пространств (плотность, аксиомы отделимости, компактность и т.д.) оказываются невыразимыми. Тем не менее, большим плюсом модальной логики S4 является ее разрешимость, которая отсутствует в логике предикатов, в которой можно выразить гораздо больше свойств топологических пространств.
Во второй части доклада я расскажу про различные способы, обогащения языка модальной логики, которые позволяют выражать больше свойств топологических пространств, оставаясь в рамках разрешимых исчислений.
В третьей части доклада я расскажу про конструкцию битопологического произведения, которая возникла в рамках развития топологических модальных логик многомерных структур. Результатом произведения двух топологических пространств является битопологическое пространство с горизонтальной и вертикальной топологиями. В горизонтальной топологии множество открыто, если все проекции горизонтальных сечений открыты. Аналогично для вертикальной топологии. Эта конструкция позволяет различить топологические пространства, которые были неразличимы в других языках. Я расскажу про результаты в этой области и открытые вопросы.
Семинар пройдет по адресу Покровский бульвар 11, аудитория R306.
Информация о семинаре и аннотация предстоящего доклада: https://cs.hse.ru/seminatfkn/
Регистрация: https://cs.hse.ru/big-data/polls/788384338.html
➰ ВК
🔥2👍1
#матлог #учёба #спецсеминар
25 февраля 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
С. Л. Кузнецов (МИАН)
Эффективная неотделимость и её применения для теорий с неподвижными точками (вторая часть)
Аннотация:
Техника эффективной неотделимости позволяет доказывать теоремы об алгоритмической неразрешимости и $\Sigma^0_1$-полноте логических теорий в ситуациях, когда прямое сведение известных задач, таких как задача останова машины Тьюринга, построить не получается. Будет рассказано об эффективной неотделимости, приведена новая пара эффективно неотделимых множеств — нетотальных контекстно-свободных грамматик и так называемых регулярно тотальных контекстно-свободных грамматик. Далее с помощью этой пары будет доказана $\Sigma_0^1$-полнота эквациональных теорий алгебр Клини с делениями и алгебр Хомского — идемпотентных полуколец с оператором взятия наименьшей неподвижной точки.
Доклад частично основан на недавней совместной работе автора с А. Дасом и А. Де.
Доклад планируется на два заседания семинара.
➰ ВК
25 февраля 2026 г. состоится заседание Рабочего семинара по математической логике под руководством С.Л. Кузнецова и С.О. Сперанского, в рамках НОЦ МИАН.
Время начала: 16:00
Место: МИАН (ул. Губкина, 8), ауд. 303
Всех слушателей просим зарегистрироваться на странице семинара: www.mathnet.ru/conf2533
С. Л. Кузнецов (МИАН)
Эффективная неотделимость и её применения для теорий с неподвижными точками (вторая часть)
Аннотация:
Техника эффективной неотделимости позволяет доказывать теоремы об алгоритмической неразрешимости и $\Sigma^0_1$-полноте логических теорий в ситуациях, когда прямое сведение известных задач, таких как задача останова машины Тьюринга, построить не получается. Будет рассказано об эффективной неотделимости, приведена новая пара эффективно неотделимых множеств — нетотальных контекстно-свободных грамматик и так называемых регулярно тотальных контекстно-свободных грамматик. Далее с помощью этой пары будет доказана $\Sigma_0^1$-полнота эквациональных теорий алгебр Клини с делениями и алгебр Хомского — идемпотентных полуколец с оператором взятия наименьшей неподвижной точки.
Доклад частично основан на недавней совместной работе автора с А. Дасом и А. Де.
Доклад планируется на два заседания семинара.
➰ ВК
👍1
#матлог #учёба #школа
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
23 – 28 марта 2026 мы проводим весеннюю школу, https://llfp.hse.ru/school26
➰ ВК
--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия
23 – 28 марта 2026 мы проводим весеннюю школу, https://llfp.hse.ru/school26
➰ ВК
❤2
#матлог #спецсеминар #не_мехмат #МФТИ
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 25 февраля в 14:15.
Доклад будет в онлайн формате.
Будет организована трансляция на большом экране по адресу:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Логический подход к концентрации.
Докладчик: Максим Жуковский
Аннотация.
Хорошо известно, что сумма и максимум n независимых случайных величин при некоторых ограничениях сконцентрированы вокруг своего математического ожидания. Аналогичные результаты справедливы и для многих других функций от независимых случайных величин - в частности, для числа подграфов, изоморфных заданному, в случайном графе и для максимальной степени. Мы определяем язык, термы в котором подчиняются закону концентрации - их интерпретации на случайном графе сконцентрированы вокруг их математических ожиданий. Этот результат обобщает классические законы нуля или единицы в логике первого порядка.
Доклад основан на совместной работе с Michael Benedikt.
➰ ВК
Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Страница семинара: www.mathnet.ru/rus/conf2559.
Семинар пройдет в среду 25 февраля в 14:15.
Доклад будет в онлайн формате.
Будет организована трансляция на большом экране по адресу:
МФТИ, Административный корпус, ауд. 322, Первомайская ул. д.7, Долгопрудный.
Чтобы пройти на семинар, а также для получения ссылки на интернет-трансляцию пишите на почту kudinov.andrey@gmail.com.
Название: Логический подход к концентрации.
Докладчик: Максим Жуковский
Аннотация.
Хорошо известно, что сумма и максимум n независимых случайных величин при некоторых ограничениях сконцентрированы вокруг своего математического ожидания. Аналогичные результаты справедливы и для многих других функций от независимых случайных величин - в частности, для числа подграфов, изоморфных заданному, в случайном графе и для максимальной степени. Мы определяем язык, термы в котором подчиняются закону концентрации - их интерпретации на случайном графе сконцентрированы вокруг их математических ожиданий. Этот результат обобщает классические законы нуля или единицы в логике первого порядка.
Доклад основан на совместной работе с Michael Benedikt.
➰ ВК
👍1
#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД
Logic Online Seminar (www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
02.03.2026, В.Г. Кановей: О конструктивных множествах в теории множеств Симпсона (onsite)
Теория множеств Симпсона SST получается из ZF удалением аксиомы степени и схемы аксиом подстановки (схема выделения сохраняется), и добавлением аксиом:
1) транзитивного надмножества,
2) транзитивной свёртки фундированных отношений - "аксиома Beta",
3) счётности всех множеств, и
4) декартова произведения.
Также SST можно получить из ATRset0 (по Симпсону) добавлением схемы аксиом выделения для всех теоретико-множественных формул.
Метаматематически, SST есть теория стандартной теоретико-множественной надстройки над универсумом арифметики второго порядка Z2 (без аксиомы выбора), допускает взаимно обратные интерпретации с Z2, и поэтому равнонепротиворечива с Z2.
Симпсон показал, что построение класса L всех конструктивных множеств по Гёделю осуществимо в ATRset0, тем более в SST, несмотря на отсутствие схемы аксиом подстановки/собирания, которая используется для обоснования трансфинитной индукции в ZF.
Исследуя класс L в теории Симпсона, мы доказываем, что класс L удовлетворяет самой SST без аксиомы счётности, в частности, удовлетворяет схеме аксиом выделения.
Краткий скетч доказательства даст представление о способах рассуждений в ATRset0 и SST в которых схема подстановки/собирания из ZF замещается "аксиомой Beta".
➰ ВК
Logic Online Seminar (www.mathnet.ru/rus/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk
02.03.2026, В.Г. Кановей: О конструктивных множествах в теории множеств Симпсона (onsite)
Теория множеств Симпсона SST получается из ZF удалением аксиомы степени и схемы аксиом подстановки (схема выделения сохраняется), и добавлением аксиом:
1) транзитивного надмножества,
2) транзитивной свёртки фундированных отношений - "аксиома Beta",
3) счётности всех множеств, и
4) декартова произведения.
Также SST можно получить из ATRset0 (по Симпсону) добавлением схемы аксиом выделения для всех теоретико-множественных формул.
Метаматематически, SST есть теория стандартной теоретико-множественной надстройки над универсумом арифметики второго порядка Z2 (без аксиомы выбора), допускает взаимно обратные интерпретации с Z2, и поэтому равнонепротиворечива с Z2.
Симпсон показал, что построение класса L всех конструктивных множеств по Гёделю осуществимо в ATRset0, тем более в SST, несмотря на отсутствие схемы аксиом подстановки/собирания, которая используется для обоснования трансфинитной индукции в ZF.
Исследуя класс L в теории Симпсона, мы доказываем, что класс L удовлетворяет самой SST без аксиомы счётности, в частности, удовлетворяет схеме аксиом выделения.
Краткий скетч доказательства даст представление о способах рассуждений в ATRset0 и SST в которых схема подстановки/собирания из ZF замещается "аксиомой Beta".
➰ ВК
#матлог #учёба #спецсеминар
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
We resume our seminar in 2026 with the talk of Alexey Milovanov:
Limit on the computational power of C-random strings.
Informally, the Kolmogorov complexity of a string x is defined as the minimal length of a program that outputs x on the empty input. This concept allows us to define the notion of an individual random string. Specifically, a string x is called random if its Kolmogorov complexity is at least the length of x. Let R denote the set of all random strings. A natural question is: how powerful is the oracle R? For example, what languages belong to P^R?
These and similar questions have been investigated in the works of Allender, Hirahara, and others. For example, it was shown that for every universal decompressor of plain complexity U, the class P^{R_U} contains NEXP.
However, no non-trivial upper bounds for P^{R_U} were previously known: it was not even known whether there is any universal U such that the halting problem does not belong to P^{R_U}. In this talk, it will be shown that such a U exists, which solves one of the open questions posed here: https://people.cs.rutgers.edu/~allender/papers/sigact.news.draft.pdf
➰ ВК
Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)
We resume our seminar in 2026 with the talk of Alexey Milovanov:
Limit on the computational power of C-random strings.
Informally, the Kolmogorov complexity of a string x is defined as the minimal length of a program that outputs x on the empty input. This concept allows us to define the notion of an individual random string. Specifically, a string x is called random if its Kolmogorov complexity is at least the length of x. Let R denote the set of all random strings. A natural question is: how powerful is the oracle R? For example, what languages belong to P^R?
These and similar questions have been investigated in the works of Allender, Hirahara, and others. For example, it was shown that for every universal decompressor of plain complexity U, the class P^{R_U} contains NEXP.
However, no non-trivial upper bounds for P^{R_U} were previously known: it was not even known whether there is any universal U such that the halting problem does not belong to P^{R_U}. In this talk, it will be shown that such a U exists, which solves one of the open questions posed here: https://people.cs.rutgers.edu/~allender/papers/sigact.news.draft.pdf
➰ ВК
#матлог #учёба #спецкурс
В понедельник (02 марта) в 16:45 состоится первая лекция курса В.А. Любецкого «Современные методы обработки данных» (полугодовой по выбору кафедры). Страница спецкурса: https://scs.math.msu.ru/ru/node/13460
Каждому слушателю нужно послать свои ФИО и личную электронную почту по адресу 'Konstantin Gorbunov' gorbunov@iitp.ru.
Аннотация.
Дан набор буквенных последовательностей. Синтенией называется набор их коротких подпоследовательностей, которые подобны по взаиморасположению букв и по их гомологии (которая возникает из того, что каждая буква обозначает сложный объект, например, ген). Изложение не использует материал 1-го семестра (https://scs.math.msu.ru/ru/node/8581) и не требует предварительных знаний. Сейчас этот материал доступен в рукописи. Курс может сдаваться как «годовой» (объединение материала 1-го и 2-го семестров), так и как «полугодовой» (материал весеннего семестра). Эта тема нуждается в компьютерной программе, и широко востребована в мировой практике.
➰ ВК
В понедельник (02 марта) в 16:45 состоится первая лекция курса В.А. Любецкого «Современные методы обработки данных» (полугодовой по выбору кафедры). Страница спецкурса: https://scs.math.msu.ru/ru/node/13460
Каждому слушателю нужно послать свои ФИО и личную электронную почту по адресу 'Konstantin Gorbunov' gorbunov@iitp.ru.
Аннотация.
Дан набор буквенных последовательностей. Синтенией называется набор их коротких подпоследовательностей, которые подобны по взаиморасположению букв и по их гомологии (которая возникает из того, что каждая буква обозначает сложный объект, например, ген). Изложение не использует материал 1-го семестра (https://scs.math.msu.ru/ru/node/8581) и не требует предварительных знаний. Сейчас этот материал доступен в рукописи. Курс может сдаваться как «годовой» (объединение материала 1-го и 2-го семестров), так и как «полугодовой» (материал весеннего семестра). Эта тема нуждается в компьютерной программе, и широко востребована в мировой практике.
➰ ВК