Семинар Добрушинской лаборатории

Когда: вторник 29 апреля, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Дарья Серова, Михаил Рыбаков (Тверской ГУ и МФТИ),
"NP-полнота задачи разбиения множества"

Задача разбиения множества (Partition) имеет очень простую формулировку, но является NP-полной. Формулировка задачи следующая: по (мульти)множеству А натуральных чисел требуется выяснить, можно ли разбить А на два подмножества с одинаковыми суммами элементов. Эту задачу можно сформулировать и как оптимизационную: для (мульти)множества А найти такое его разбиение на два подмножества, при котором модуль разности сумм элементов этих подмножеств является наименьшей из возможных.

В докладе будет показано простое доказательство NP-полноты (прежде всего, NP-трудности) задачи Partition. Для этого будет построено полиномиальное сведение к ней задачи SubsetSum (состоящей в том, что нужно установить для числового множества А и числа Т, имеется ли в А подмножество с суммой элементов, равной Т), к которой мы полиномиально сведем проблему CNF (проблему выполнимости булевых формул, находящихся в конъюнктивной нормальной форме). В оставшееся время мы докажем NP-трудность проблемы CNF, полиномиально сведя к ней проблему SAT (проблему выполнимости булевых формул в полном языке), а затем докажем NP-трудность проблемы SAT, используя идею классического доказательства Кука–Левина.


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

Адрес: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.
Вход в МФТИ только по пропускам или спискам. Поэтому участники БЕЗ пропусков МФТИ пришлите ЗАРАНЕЕ (до понедельника) информацию о себе и не забудьте паспорт.

#ВШМ_Добрушинский

Вокруг здания Высшей школы современной математики на кампусе МФТИ разбивают новый парк ⬇️

Перепост от коллег из музея МФТИ (в их канале много интересного, подписывайтесь)

Друзья!

Владимир Семенович Булыгин, Почетный профессор МФТИ, Наставник Физтеха, Звезда Физтеха (2023), предлагает сегодня отмечать не только Праздник весны и труда, но и День постоянной Планка!

С праздником! 🙂

#праздники

Сегодня вечером (хотя у кого-то и нерабочий день) штатно проходит студенческий семинар Алгебра, геометрия и теория чисел. А именно, состоятся два доклада учебного трека:

17:05 — С.Янжинов "Комплексная алгебраическая геометрия"

Будет что-то интересное комплексное, вокруг теории периодов и GAGA.

18:35 — А.Мятелин "Теория Кодаиры-Спенсера"

Планируется дать введение в теорию деформаций Кодаиры-Спенсера компактных комплексных многообразий. Неформально, деформацией называется голоморфное локально тривиальное расслоение. Легко видеть, что слои деформации не всегда биголоморфны друг другу. Мы построим отображение Кодаиры-Спенсера, тривиальность которого является необходимым и, при правильной трактовке, достаточным условием тривиальности деформации комплексной структуры. Далее мы обсудим различные примеры, в том числе с помощью построенной техники рассмотрим полууниверсальные деформации поверхностей Хирцебруха.

Аннотации прошедших докладов, а также обновления по предстоящим, доступны в таблице https://docs.google.com/spreadsheets/d/1lX7t_MAGoSwW22_RzHpj_HXEZDORLmiiYTXbUsLeGk8/edit?gid=0#gid=0

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

#ВШМ_АГТЧ

Друзья, время анонса!
Этим летом ФПМИ и ВШМ МФТИ, МКН СПбГУ и факультет математики ВШЭ проводят ЛИПС-25 (Летнюю Исследовательскую Программу Студентов) на базе Лаборатории комбинаторных и геометрических структур ФПМИ МФТИ.

Когда? С 7 июля по 8 августа
Где? Долгопрудный, Москва
Для кого? Для студентов 3-4 курсов бакалавриата, магистров, аспирантов математических специальностей

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

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

Открыт набор студентов для участия в программе. Будем очень благодарны за репост в профильные математические паблики и чаты! :)

Заявки на участие принимаются до 15 мая.

#ВШМ_ЛИПС

Семинар Добрушинской лаборатории

Когда: вторник 13 мая, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Михаил Цфасман (МФТИ),
"Плотные упаковки шаров: обзор результатов и алгеброгеометрические конструкции"

Я расскажу сегодняшнюю ситуацию с задачей о плотных упаковках равных шаров в R^n. В небольших размерностях, помимо классики, имеются знаменитые результаты Вязовской и результат Мусина о контактном числе. В больших размерностях (когда n стремится к бесконечности) сегодня идет борьба за логарифмические члены стохастическими методами. Но кроме того, имеются явные конструкции исходя из полей алгебраических чисел и кривых над конечным полем.


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

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

#ВШМ_Добрушинский

Если вы уже прочитали всё, что откладывали себе на длинные выходные, но еще не видели это интервью научного руководителя Высшей школы современной математики Михаила Цфасмана о новом Абелевском лауреате Масаки Касиваре — почитайте! А если уже читали — присоединяйтесь во вторник к трансляции доклада Цфасмана на Добрушинском семинаре ⬆️ или приходите на 3 этаж Административного корпуса, чтобы послушать его вживую

Семинар Добрушинской лаборатории

Когда: вторник 20 мая, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Михаил Цфасман (МФТИ),
"Плотные упаковки шаров: обзор результатов и алгеброгеометрические конструкции. Часть 2"

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


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

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

#ВШМ_Добрушинский

Памяти Е. А. Печерского (1937-2025)

В ночь на 20 мая скончался Евгений Абрамович Печерский — один из старейших сотрудников Добрушинской математической лаборатории ИППИ РАН, в которой он работал начиная с 1989 года и до последнего времени. Его основной научной тематикой являлось исследование задач, связанных с теорией больших уклонений в задачах математической физики. По этой тематике он защитил диссертацию на степень кандидата физико-математических наук в 1975 году.

Пожалуй, наиболее заметным математическим результатом Печерского является цикл совместных работ с Р. Л. Добрушиным, в которых был доказан принцип больших уклонений для процессов с независимыми приращениями в форме, удобной для применений к системам массового обслуживания. В другой совместной работе с Р. Л. Добрушиным был получен критерий единственности гиббсовского состояния для некомпактного спинового пространства. Этот критерий использовался для исследования области единственности состояния неидельного газа.

В дальнейшем полученные Е. А. Печерским результаты нашли многочисленные приложения в задачах массового обслуживания (в его совместных работах с Н. Д. Введенской и Ф. И. Карпелевичем), а также в некоторых применениях теории гиббсовских полей к задачам обработки изображений.

Евгения Абрамовича со многими из нас связывали прочные связи — не только научные, но и искренне человеческие. Постоянные участники Добрушинского математического семинара, а также семинара Р. А. Минлоса на механико-математическом факультете МГУ помнят мягкую манеру Евгения Абрамовича, его искренний интерес к работам коллег — как опытных исследователей, так и только начинающих свой путь в математике. Светлая память о Е. А. Печерском и влияние его работ сохранятся надолго.

Выносим из комментариев к предыдущей записи:

Увы, одновременно с Евгением Абрамовичем не стало еще одного старейшего сотрудника ИППИ, Петра Петровича Николаева — и хотя он работал как биолог, но при этом был большой знаток старых работ XIX века по проективной геометрии! Вот небольшой текст о нем, в котором, правда об этих математических увлечениях не сказано

Семинар Добрушинской лаборатории

Когда: вторник 27 мая, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Олег Мусин (University of Texas Rio Grande Valley),
"Теоремы существования и быстрые алгоритмы для задач справедливого дележа / Existence theorems and fast algorithms for fair division problems"

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

Вторая часть доклада — это совместная работа, которая была мотивирована публикацией в New York Times: "To Divide the Rent, Start With a Triangle" by Albert Sun (April 28, 2014)", к которой прилагается калькулятор для справедливой аренды, основанный на работе Фрэнсиса Су. В недавно опубликованной статье мы рассматриваем алгоритмическую сложность задач справедливого дележа и минимизацию количества запросов необходимых для нахождения приближенного решения с желаемой точностью. Для нескольких классов задач справедливого дележа показано, что при определенных естественных условиях на множествах предпочтений достаточно логарифмического количества запросов относительно точности.

#ВШМ_Добрушинский

Логический семинар лаборатории им. Манина

Когда: среда 4 июня, 14:00
Где: Адм. корпус, ауд.322.

Доклад:

В.Б. Шехтман, А.В. Кудинов,
"О семантической полноте суперинтуиционистских и модальных логик"

Суперинтуиционистские логики были одним из основных направлений исследований А.В. Кузнецова, и проблемы полноты играют в этом контексте ключевую роль. В частности, Кузнецов поставил проблему о совпадении полноты по Крипке и топологической полноты. В статье Шехтмана "On Neighbourhood Semantics Thirty Years Later, 2005“ приведен контрпример, доказывающий, что топологическая полнота сильнее, чем семантика Крипке, но без явной аксиоматизации. Такие же примеры известны для модальных логик, содержащих S4. В докладе обсуждаются другие аналогичные примеры для суперинтуиционистских и модальных логик. В частности, будет дан пример конечно аксиоматизируемой модальной логики с 3 модальностями, которая полна в окрестностной семантике относительно счетной шкалы, но неполна в семантике Крипке.


Планируется интернет-трансляция по адресу https://telemost.yandex.ru/j/00084330909943

Сртаница семинара: https://www.mathnet.ru/rus/conf2559

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

#ВШМ_логический

Докладчики:
Екатерина Преснова (ВШЭ)
Екатерина Америк (ВШЭ, Paris-Saclay)
Дмитрий Фроленков (МИАН)
Владлен Тиморин (ВШЭ, НМУ)

Начало конференции 11 июня в 12:00 в большом конференц-зале МИАН (ул. Губкина, д. 8, 9 этаж)
http://zykin.mccme.ru

Семинар Добрушинской лаборатории

Когда: вторник 17 июня, 16:15
Где: Адм. корпус, ауд.322.

Доклад:

Valentin Zagrebnov (Universty Aix-Marseille),
"What do we actually know about the operator-norm convergent Trotter-Kato product formula?"

Since 1875 due to Sophus Lie it is known that for any pair of (noncommutative) finite square matrices A and B as generators one has the norm estimate O(1/n) for convergence rate of the exponential product formula. In 1959 H.Trotter proved this formula in the strong operator topology on the Banach space for strongly continuous semigroups and unbounded generators A and B. Further, in 1978 T.Kato extended this result (still in the strong operator topology) to the non-exponential product formulae.

A breakthrough result in this direction was presented in the Dzh.L.Rogava theorem (1993). It says that on a separable Hilbert space the exponential Trotter product formula may converge in the operator-norm topology with convergence rate of the order O(ln(n)/sqrt(n)). This discovery initiated a number of papers addressed to the study of conditions on generators A and B aiming to optimise the rate of convergence in Rogava’s assertion.

Motivated by this discovery the optimal rate of convergence O(1/n) in the operator-norm topology under conditions of the Rogava theorem was proved only in 2001 (the Ichinose-Tamura-Tamura-Zagrebnov theorem) for both the Trotter and the Trotter-Kato product formulae. Under new fractional conditions on generators A and B the optimal rate of the Trotter-Kato product formulae convergence in the operator-norm topology on a Hilbert space was established in the Ichinose-Neidhardt-Zagrebnov (INZ)-theorem (2004).

I shall present these and some other recent results about the Lie-Trotter-Kato product formulae on Hilbert and Banach spaces, which are collected in the book: V.A.Zagrebnov, H.Neidhardt, T.Ichinose, Trotter-Kato Product Formulae, 2024.


Планируется интернет-трансляция по адресу:
https://telemost.yandex.ru/j/81255480783695
Регистрируйтесь вашей фамилией, а не псевдонимом!

Страницы семинара:
https://sites.google.com/view/dobr-seminar
https://www.mathnet.ru/conf167

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

#ВШМ_Добрушинский

Вопрос по поступлению в ВШМ? Задайте его здесь — в комментариях.

На время приемной кампании (до начала августа 2025) этот пост будет закреплен.

Присутствие сотрудников ВШМ на стенде гарантировано каждые вт и чт с 10:30 до 17:30 (с перерывом на обед 13:00-14:00). В остальные дни — по предварительной договоренности. На стенде всегда есть запас буклетов и объявление с контактами, чтобы можно было с нами связаться

Выше в этом канале:
- наш обзор правил поступления на Физтех в 2025;
- видео выступления директора ВШМ Андрея Соболевского на Дне открытых дверей МФТИ.

Физтех, прием! В МФТИ стартовала приемная кампания в бакалавриат