Семинары ПОМИ
С. В. Иванов: "Положительная энтропия в КАМ-теории. Часть 2." | 07.11.19, 16:00
Во второй части я расскажу основные моменты доказательства основного
результата: для любой интегрируемой гамильтоновой системы существуют сколь угодно малые возмущения с положительной локально генерируемой метрической энтропией.
А.В.Смоленский: "О структуре бесконечных систем корней" | 11.11.19, 11:30
Бесконечные системы корней естественным образом возникают при изучении алгебр Каца—Муди, обобщающих полупростые конечномерные алгебры Ли над полем комплексных чисел. В докладе будут рассмотрены некоторые их неожиданные комбинаторные и геометрические свойства, связанные с вычислением централизаторов корневых подгрупп.
С. В. Иванов: "Положительная энтропия в КАМ-теории. Часть 1." | 31.10.19, 16:00
Доклад по совместной работе с D. Burago и D. Chen.
В серии из двух докладов я расскажу доказательство следующего результата:
для любой интегрируемой гамильтоновой системы существуют сколь угодно малые возмущения гамильтониана такие, что возмущенная система имеет положительную метрическую энтропию, причем энтропия генерируется в сколь угодно малой окрестности одной периодической орбиты. Например, интегрируемой системой является геодезический поток плоского двумерного тора, в этом случае возмущенная система реализуется геодезическим потоком финслеровой метрики.
В первой части будет обзор необходимых понятий и сведений о гамильтоновых системах вообще и интегрируемых системах в частности, а также план доказательства основного результата.
М.А.Антипов: "О некоторых вопросах классификации алгебр ручного типа представления" | 04.11.19, 11:30
А. И. Назаров, Спектральные асимптотики и асимптотики малых уклонений для некоторых ДБД-подобных процессов
А. В. Смирнов: "Гиперболичность высших рангов" | 24.10.19, 16:00
по работе У. Лэнга и Б. Кляйнера
Пятница 25.10. Дмитрий Соколов: "(Semi)Algebraic proofs over $\{\pm 1\}$ variables"
Пятница, 25 октября, ауд. 106. Начало в 17:00.
Докладчик: Дмитрий Соколов.
Тема: (Semi)Algebraic proofs over variables.Abstract In this talk, we study versions of Polynomial Calculus and Sum-of-Squares proof systems. Current techniques for size lower on these proof systems bounds significantly use {0, 1} encoding of variables. More formally, we need to be able to assign any variable by a feasible value in a way to kill a term, that helps us to reduce a question about size to a question about degree.
We know the for ``Fourier'' encoding of boolean variables degree lower bound is not enough to prove size lower bounds [Buss et al. 2001]. In this talk we present show exponential lower bounds on monomial size of proofs in SoS and PCR as well as separation between these systems. It is a solution to an open problem from [Impagliazzo, Mouli, Pitassi 2019].
Д. Н. Запорожец, Среднее расстояние между случайными точками.
В. Золотов: "Жадные вложения деревьев" | 17.10.19, 16:00
Известно, что дерево обладающее даблингом с константой M допускает би-липшицево вложение в Евклидово пространство, причем размерность пространства и дисторшен отображения ограничены сверху константами зависящими только от M.
Lee, James R., Assaf Naor, and Yuval Peres. "Trees and Markov convexity." Geometric and Functional Analysis 18.5 (2009): 1609-1659.
Оказывается, если подставить идеи из известных доказательств в жадный алгоритм, то доказательство существенно упростится. Об этом и будет доклад.
К.И.Пименов: "Свойство поднятия и ортогоналы в элементарной топологии и теории групп" | 21.10.19, 11:30
И. С. Алексеев, Growth rate of braid groups
Й. Стоянов, Characterization of Probability Distributions Via Semi-Invariants and/or Moments
Пятница 11.10. Святослав Грязнов: "Нижняя оценка на степень вывода слабого принципа Дирихле с использованием метода pigeon dance"
Пятница, 11 октября, ауд. 106. Начало в 17:00.
Докладчик: Святослав Грязнов (ПОМИ РАН).
Тема: Нижняя оценка на степень вывода слабого принципа Дирихле с использованием метода pigeon dance.Abstract Мы докажем теорему Разборова о нижней оценке на степень доказательства невыполнимости слабого принципа Дирихле (WPHP) в системе доказательств Polynomial calculus. Данный метод был предложен в статье [1]. В статье вводится понятие так называемоего "pigeon dance", который представляет из себя некоторый недетерминированный процесс рассадки кроликов по клеткам. Позднее данная техника была использована в статье [2], в которой Импаляццо, Пудлак и Сгалл доказали более общее утверждение о минимальном количестве используемых мономов в любом PC-доказательстве невыполнимости произвольной формулы.
[1] A. A. Razborov, Lower Bounds for the Polynomial Calculus, Computational Complexity, 7(4), (1998)
[2] R. Impagliazzo, P. Pudlák, and J. Sgall, Lower bounds for the polynomial calculus and the Groebner basis algorithm, Comput. Complexity, 8(2), (1999)
Д. В. Карпов: "О хроматическом числе 2-планарного графа" | 14.10.19, 11:30
С. С. Подкорытов, Скромность отображений $S^1\to Y$
К. С. Рядовкин, О ветвящихся случайных блужданиях на периодических графах
Г. Ю. Панина: "О честном делении ожерелья и теоремах типа Тверберга" | 10.10.19, 16:00
Теоремы типа Тверберга говорят о наличии (при определенных условиях) r-кратных пересеченийобразов граней симплициального комплекса.
Теорема о честном делении ожерелья, говорит, что для честного деления между r ворами ожерелья (=отрезка) с сидящими на нем n мерами достаточно n(r-1) разрезов.
Несмотря на разницу формулировок, задачи родственны между собой. Мы обсудим историю вопроса и новые результаты,
см. препринты D. Jojić, G. Panina, R. Živaljević
"A tverberg-type theorem for collectively unavoidable complexes", arXiv:1812.00366
и "Splitting necklaces, with constraints", arXiv:1907.09740
Русский
English