Семинары

28.01, 18:10 Задача подсчета количества целых точек в k-модулярных симплексах и близких полиэдрах

Ссылка на конференцию Zoom

Пароль необходимо запросить у менеджера лаборатории

Докладчик: Дмитрий Грибанов, младший научный сотрудник лаборатории алгоритмов и технологий анализа сетевых структур факультета информатики, математики и компьютерных наук НИУ ВШЭ

Аннотация. Рассмотрим симплекс, заданный системой вида A x <= b, где A и b - есть целочисленные матрица и вектор. Симплекс называется k-модулярным если абсолютная величина ранговых миноров матрицы A ограничена числом k. На докладе будет показано, что задача подсчета целых точек внутри k-модулярных симплексов разрешима за полиномиальное время, если фиксировать k. Также в докладе будут рассмотрены возможные обобщения этого факта и различные частные случаи, допускающие более эффективные алгоритмы решения.

24.12, 18:10 Towards Dynamic-Point Systems on Metric Graphs with Longest Stabilization Time

Speaker: L.W. Dworzanski

A dynamical system of points moving along the edges of a metric graph is a discrete dynamical system. For the set of such systems that can be constructed from a given set of commensurable edges with fixed lengths, it is shown that there always exists a system consisting of a bead graph with vertex degrees not greater than three that demonstrates the longest stabilization time in such a set.

10.12, 18:10-19:30 Efficient Computation of Distances between Persistence Diagrams

Speaker: Arnur Nigmetov, Lawrence Berkeley National Laboratory

I am going to talk about algorithms for computing the bottleneck and Wasserstein distances between persistence diagrams (and their implementation in a software package called Hera). Both distances are defined in terms of a graph matching problem (bottleneck matching and min-cost maximum matching, for bottleneck and Wasserstein cases, respectively). Moreover, the graphs in this case are geometric, i.e., the weight of each edge is the distance between the points of two diagrams. It turns out that one can speed up classical combinatorial algorithms for solving these matching problems by using data structures from computational geometry.

 

3.12, 18:10-19:30 Персистентная гомология в ГИС-приложениях

Докладчик:Сергей Еремеев (Владимирский государственный университет) по совместной работе с Дмитрием Андриановым и Виталием Титовым

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

26.11, 18:00 - 19:00 Topological data analysis of eye movements

Speaker: Arseniy Onuchin (4-th grade student, Faculty of Psychology, MSU) 

The increasing use of eye-tracking in modern cognitive and clinical psychology, neuroscience and ophthalmology requires new methods of objective quantitative analysis of complex eye movements data. In their work, the authors use topological data analysis (TDA) to extract a new type of features of eye movements to differentiate between two eye movements groups, obtained upon the presentation of two different stimuli images – a human face, shown straight and rotated for 180 degrees, which corresponds to the processing of the normal and unusual visual information respectively. Experimental evidence shows that the proposed topology-based features have more discriminative power over the generally accepted features of eye movements, allowing to separate provided different stimuli with good accuracy. Moreover, the concatenation of the topology-based and region of interest fixation ratios features further improves the performance of the classification task, showing the complementariness of the proposed topological features to the existing ones. The authors believe that the new class of features is able to serve as a valuable addition for the eye-tracking data-based medical diagnosis of mental and neurological disorders and ophthalmological diseases.

23.11, 15:00 The coalgebra of chains and the fundamental group

Speaker: Manuel Rivera (Purdue)

Rational homotopy theory tells us that simply connected spaces, up to rational homotopy equivalence, may be classified algebraically by means of rational cocommutative coalgebras (Quillen) or in the finite type case by rational dg commutative algebras (Sullivan). Goerss and Mandell proved versions of these results for fields of arbitrary characteristic by means of simplicial cocommutative coalgebras and E-infinity algebras, respectively. The algebraic structures in these settings are considered up to quasi-isomorphism.
In this talk, I will describe how to extend these results to spaces with arbitrary fundamental group. The key new observation is that the homotopy cocommutative coalgebraic structure of the chains on a space determines the fundamental group in complete generality. The corresponding algebraic notion of weak equivalence between coalgebras is drawn from Koszul duality. The end goal of this program is to completely understand homotopy types in terms of algebraic “chain level” structure. This is joint work with M. Zeinalian and F. Wierstra.

4.11 Топологический анализ данных в применении к задачам обработки текстов

Докладчик: Лаида Кушнарева (МГУ, Хуавей)

Мы расскажем о современных подходах к изучению топологии многообразий данных, а также представим нашу работу по построению информативных топологических представлений текстов, основанных на нейросетевых вложениях. Нейросетевая модель BERT позволяет каждому небольшому тексту сопоставить многомерный вектор, отражающий смысл текста. Оказалось, что если вместо него в задачах классификации использовать значительно меньший объем информации, полученной из топологии нейросети в BERT, классификация будет столь же или даже более эффективной. Тут возникает ряд новых задач, которые могут быть интересны аспирантам и студентам.

29.10, 18:10-19:30 Extendability of simplicial maps is undecidable

Покровский бульвар 11, ауд. D211

Докладчик: Arkadiy Skopenkov, Moscow Institute of Physics and Technology, and Independent University of Moscow

We explain why the problem of extendability of simplicial maps is interesting to computer scientists. In particular, we illustrate the relation to polygonal lines in the plane, to words in finite alphabets, and to realizability of hypergraphs in higher-dimensional space.We present a short proof of the Čadek-Krčál-Matoušek-Vokřínek-Wagner 2013 result from the title (in the following form due to Filakovský-Wagner-Zhechev, 2020).For any fixed integer l>1 there is no algorithm recognizing the extendability of the identity map of the wedge Y of two l-dimensional spheres to a PL map from X to Y for a given 2l-dimensional simplicial complex X containing a subdivision of Y as a given subcomplex.
 In this talk topological concepts are exposed in the way interesting and accessible to non-specialists, in particular, to computer science students.

22.10, 18:10-19:30 Циклические заполняющие пространство кривые и их кластеризующее свойство

Докладчик: Игорь Нетай (НПК Криптонит и ИППИ РАН)

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

15.10, 18:10 Вычисление топологических характеристик с помощью комбинаторных лапласианов; Классификация представлений колчанов и представлений с коммутативными ограничениями

Докладчик: Полина Борисова (студентка магистратуры факультета математики НИУ ВШЭ,  стажер-исследователь МЛ АТиП).

Название:  Вычисление топологических характеристик с помощью комбинаторных лапласианов

 Многие знают, что такое оператор Лапласа на пространстве гладких функций, но не все знают, что аналогичный оператор можно определить и на цепном комплексе. Именно такой оператор часто возникает, когда мы хотим понять структуру симплициального комплекса. Например, подсчет чисел Бетти можно свести к вопросу о поиске определенных собственных значений лапласиана. К аналогичному вопросу можно свести и выявление в гомологиях симплициального комплекса порождающих циклов.«Классификация представлений колчанов и представлений с коммутативными ограничениями».

Докладчик: Никита Калинин (студент бакалавриата факультета компьютерных наук НИУ ВШЭ).

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

Теория колчанов неожиданным образом проникла в множество разделов математики от теории представлений и матричных задач до теории персистентности. В своем рассказе Никита опишет мотивацию использования колчанов в топологическом анализе данных, представит классические результаты классификации представлений и достаточно новые результаты о классификации с ограничениями. В качестве последних будут рассмотрены колчаны специального типа - так называемые "лесенки".

8.10 Оценка матрицы ковариации, распадающейся в тензорное произведение

Докладчик: Дмитрий Трушин, доцент ДБДиИП, ФКН ВШЭ

Базовая задача звучит так: пусть есть случайный вектор xi на евклидовом пространстве V со средним ноль и матрицей ковариацией s (положительно определенная матрица). Мы хотим оценить s по независимой выборке x_1,...,x_d из V. Такая оценка обычно ищется из минимизации некоторой целевой функции. Есть два классических примера:

1) На основе гауссовского распределения.

2) На основе эллиптического распределения.

Самый важный показатель — минимальный размер выборки для существования и единственности минимума. В первом случае — это n, во втором — n + 1.

Обычно в задачах d сильно меньше n и приходится рассматривать дополнительные условия на распределение. Например, xi живет в тензорном произведении V\otimes U (dim V = n и dim U = m), центрирована, а матрица ковариации имеет вид s = p\otimes q. В этом случае элементы выборки x_1,...,x_d можно рассматривать как матрицы. Как оказалось, в обоих случаях оценку на размер выборки можно улучшить и граница становится m/n + n/m. Данные оценки уже не улучшаемые.

Сам вопрос о наличии нетривиальной оценки в случае тензорного произведения оставался открытым почти 20 лет. Обзор событий и подробную информацию о задачах, использующих тензорное произведение, можно найти в статье

I. Soloveychik, D. Trushin, Gaussian and robust Kronecker product covariance estimation: Existence and uniqueness, Journal of Multivariate Analysis 149 (2016), 92-113.

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

1.10, 18:10 The mergegram of a dendrogram and its stability.

Speaker: Yury Elkin, University of Liverpool, PhD Student.

TDA quantifies topological shapes hidden in unorganized data such as clouds of unordered points. In the 0-dimensional case the distance-based persistence is determined by a single-linkage (SL) clustering of a finite set in a metric space. Equivalently, the 0D persistence captures only edge-lengths of a Minimum Spanning Tree (MST). Both SL dendrogram and MST are unstable under perturbations of points. We define the new stable-under-noise mergegram, which outperforms previous isometry invariants on a classification of point clouds by PersLay.

24.09 Обработка данных нейронной активности в гиппокампе грызуна; Вычислительный оптимальный транспорт и поиск барицентров Вассерштейна; Описание класса комплексного кобордизма торического многообразия

Докладчик: Константин Сорокин, магистрант 2-го курса Матфака ВШЭ, стажер лаборатории.

Название: Обработка данных нейронной активности в гиппокампе грызуна

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

Докладчик: Даниил Тяпкин, студент ОП ПМИ ФКН ВШЭ, 4 курс.

Название: Вычислительный оптимальный транспорт и поиск барицентров Вассерштейна

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

Докладчик: Владимир Смурыгин, студент программы ПМИ ФКН ВШЭ, 4 курс.

Название: Описание класса комплексного кобордизма торического многообразия

Старая задача в алгебраической топологии - описание коэффициентов экспоненты формальной группы комплексных кобордизмов. Имеется гипотеза Бухштабера о явном виде этих коэффициентов. Мы хотим численно проверить (или опровергнуть) эту гипотезу, написав программу для подсчета характеристических чисел торических многообразий, основанную на дифференцировании многочлена объема.

24.07 Complexes of Tournaments in Directed Networks

Speaker: Ran Levi, professor at University of Aberdeen.

Clique graphs whose edges are oriented are referred to in the combinatorics literature as tournaments. We consider a family of semi-simplicial sets, that we refer to as “tournaplexes", whose simplices are tournaments. In particular, given a directed graph G, we associate with it a “flag tournaplex" which is a tournaplex containing the directed flag complex of G, but also the geometric realisation of cliques that are not directed. We define several types of filtration on tournaplexes, and exploiting persistent homology, we observe that filtered flag tournaplexes provide finer means of distinguishing graph dynamics than the directed flag complex. We then demonstrate the power of those ideas by applying them to graph data arising from the Blue Brain Project’s digital reconstruction of a rat’s neocortex.

3.07 Image processing and controlled linear algebra

Докладчик: Ильяс Байрамов, магистрант 2-го курса Матфака ВШЭ.

In 1996, Michael Freedman, famous for the results in the classification of 4-manifolds, decided to apply its methods in image processing. He and his co-author employed a curious method of altering the matrix of the district wavelet transform, instead of introducing the usual window, to reduce Gibbs (edge) effects. This method is based on a deep theory behind the classification result, specifically, an enhancement of the famous Kirby torus trick. I would like to explain these methods, and their extension by Freedman to quantum computing.

12.06 Торическая персистентная топология в комбинаторной теории графов.

Докладчик: Елизавета Стрельцова, Мехмат МГУ, студентка 6 курса.

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

Классические и новые характеристики являются функциями на множествах графов и симплициальных комплексов. Для случайных графов и комплексов эти характеристики становятся случайными величинами. В ряде работ по вероятностной топологии рассматривается вероятностное пространство случайных d-мерных симплициальных комплексов. В докладе будет введена новая целочисленная случайная величина на этом пространстве – вещественное число Бухштабера.

Будут рассказаны как результаты вычислений, так и оценки и свойства этой случайной величины.

5.06 Сдавливание и свободная деформационная ретракция.

Докладчик: Алексей Горелов, Матфак ВШЭ, магистрант

Назовём свободной деформационной ретракцией строгую деформационную ретракцию, для которой выполнено $f_t f_s = f_\max(t,s)$. Д.Р. Исбелл (Isbell, 1964) показал, что для двумерных компактных полиэдров существование свободной деформационной ретракции на точку эквивалентно сдавливаемости на точку. Конструкция Берштейна-Коэна-Конелли (Berstein, Cohen, Connelly, 1978) показывает, что для полиэдров размерности больше четырёх это неверно: существуют свободно деформационно ретрагируемые на точку несдавливаемые полиэдры. В совместной работе с Сергеем Мелиховым докладчик доказал, что если потребовать от свободной деформационной ретракции кусочно-линейность, то её существование эквивалентно сдавливаемости.

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

29.05 Disease progression models

Speaker: Boris A. Gutman, PhD, Assistant Professor of Biomedical Engineering, Armour College of Engineering, Illinois Institute of Technology

As humans, we like to predict all manner of things, not least of them being our physical health. And while there is much excitement in the world of artificial intelligence about the ever-improving accuracy with which we can predict things, we are often less concerned with domain-specific relevance and utility of the prediction. Simple binary questions such as “does this patient have disease X?” or even “will the patient acquire disease X in Y years?” have proven less interesting to basic researchers and health professionals than “how quickly will the patient’s health deteriorate?”, “when and in what order will future symptoms appear?” and “what are the connections among the observable biomarkers and between biomarkers and symptom onset?”

Disease progression models (DPMs) attempt to answer the more interesting questions. In this talk, we will focus on applications of DPMs to brain imaging and neurodegenerative disease. I will go over some recent imaging-DPM developments from simple Bayesian models describing temporal biomarker order to differential equation models linking brain structure, connectivity and prior neurobiological knowledge to dynamically predict the course of an individual’s neurodegeneration.

15.05 Теорема Квиллена-МакКорда и ее вариации

Докладчик – Виталий Гузеев, студент факультета математики НИУ ВШЭ.

Частный случай теоремы Квиллена А (известный как теорема Квиллена-МакКорда) позволяет доказывать гомотопическую эквивалентность частично упорядоченных множеств при определенных условиях. Джонатан Бармак в статье 2000-го года приводит доказательство этой теоремы, использующее интересный объект - цилиндр отображения частично-упорядоченных множеств.
В докладе будет разобрано это доказательство, а также аналогичное доказательство гомологической версии теоремы Квиллена. Требуемые для понимания топологические конструкции будут объяснены в ходе доклада. 
Докладчик также расскажет о приближенной гомологической версии теоремы Квиллена, - гипотетическом обобщении этой теоремы на устойчивые гомологии, и предложит подход к ее доказательству. Подход основан на идеях Бармака и технике спектральных последовательностей. Похожие соображения можно найти в статье Govc, Skraba, An Approximate Nerve Theorem 2017 года, но,кажется, что их можно естественным образом обобщить.

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

08.05 Многомерные расширители

Докладчик – Константин Голубев, постдок департамента математики Швейцарской высшей технической школы Цюриха (ETH Zürich)

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

24.04 Канонические формы = диаграммы персистентности

Докладчик – Сергей Александрович Баранников, Сколтех, Paris Diderot University

Фильтрованный комплекс над полем F приводится линейными преобразованиями, сохраняющими фильтрацию, к так называемой канонической форме, то есть к канонически определенной прямой сумме фильтрованных комплексов двух типов: одномерных фильтрованных комплексов с тривиальным дифференциалом: d(e_{t_i})=0 и двумерных фильтрованных комплексов с тривиальными гомологиями: d(e_{s_j})=e_{r_j}. В докладе будет разобрано доказательство этой теоремы, которое впервые было опубликована в работе докладчика 1994 года “Framed Morse and its invariants“ Adv. in Sov. Math, 21:93-115. В этой работе эти инварианты, называемые канонической формой фильтрованного комплекса, были применены к комплексам Морса, которые вычисляют sublevel гомологии функций. 
Начиная с середины 2000-х годов эти инварианты получили широкое применение в прикладной математике под именем «persistence diagrams» или  «persistence barcodes». Вышеупомянутый результат в прикладной математике обычно называется Persistence homology Main (or Structure, or Principal) Theorem.
Любопытно, что в прикладной математике в наиболее раннем исследовании по этим инвариантам также рассматривались в качестве основного примера фильтрованного комплекса именно комплексы Морса, в частном случае многообразий размерности 2. 
В качестве примеров фильтрованных комплексов часто возникают другие всевозможные комплексы (Чеха, симплициальные, кубические и т.д.) для гомологий топологического пространства, на котором задана вещественная функция. 
Последние годы в качестве функции в приложениях часто берётся функция на евклидовом пространстве, заданная евклидовым расстоянием до облака точек. 
В настоящее время существует более 10 разных софтверных платформ, посвящённых вычислению этих инвариантов. В основе этих платформ лежит алгоритм приведения фильтрованного комплекса к канонической форме, описанный в работе докладчика при доказательстве упомянутой теоремы. 
Кроме доказательства теоремы и алгоритма мы разберём также некоторые их приложения в чистой и прикладной математике. 

17.04 Факторизация торических отображений и поиск общего подразбиения треугольника

Докладчик – Александр Перепечко, научный сотрудник ИППИ и МФТИ.

В 1978 году Тадао Ода выдвинул гипотезу о сильной факторизации морфизмов торических многообразий:Любое торическое (т.е. эквивариантное) бирациональное отображение между двумя полными гладкими торическими многообразиями X и Y раскладывается в композицию цепочки торических раздутий и цепочки торических стягиваний (операций, обратных к раздутиям).
Комбинаторно полное торическое многообразие описывается полным веером рациональных полиэдральных конусов, а раздутие - подразбиением этого веера. Известно, что любое торическое бирациональное отображение описывается цепочкой таких подразбиений и обратных к ним - это слабая факторизация. Гипотеза Оды же гласит, что можно их упорядочить, произведя сначала все подразбиения, а потом - обратные операции. В частности, для вееров многообразий X и Y существует общее подразбиение, описывающее отображение между многообразиями.
В трёхмерном случае гипотеза сводится к существованию общего подразбиения у любой пары подразбиений треугольника (т.е. двумерного симплекса). В 2009 году в работе Сильвы и Кару (arXiv:0911.4693) был предложен алгоритм, который гипотетически всегда находит общее подразбиение. Мы опишем, как устроены подразбиения треугольника, соответствующие раздутиям трёхмерных торических многообразий, и разберём данный алгоритм.
На практике этот алгоритм можно упростить, и задача поиска наименьшего общего подразбиения вычислительно сложна. Теоретически, общее подразбиение могло бы служить секретом, восстанавливаемым по паре заданных подразбиений. Я предлагаю слушателям обратную задачу: придумать эффективный алгоритм подбора по случайным образом сгенерированному секрету такой пары подразбиений, чтобы секрет являлся их наименьшим общим подразбиением. Подобный алгоритм дал бы одностороннюю функцию, возможно, пригодную для нужд криптографии. 

10.04 The random simplicial complexes and toric topology

Speaker -  Djordje Baralic, Mathematical Institute of the Serbian Academy of Sciences and Arts

03.04 Фуллерены и торическая топология

Докладчик - Николай Юрьевич Ероховец, доцент Механико-математического факультета МГУ

В докладе планируется дать краткий обзор математической теории фуллеренов и её связи с торической топологией.
Фуллерен - этот трёхмерный простой выпуклый многогранник, все грани которого являются пятиугольниками и шестиугольниками. Такие многогранники моделируют сферические молекулы углерода, за открытие которых в 1996 году была дана Нобелевская премия по химии.
Одной из основных задач метематической теории фуллеренов является перечисление фуллеренов и структурирование их множества. Из результатов Тёрстона следует, что число фуллеренов с n вершинами растёт как n^9. Известны несколько эффективных методов перечисления фуллеренов. Один из них основывается на операциях роста, переводящих комбинаторый многогранник в другой многогранник с большим числом граней заменой диска на его поверхности другим диском с большим числом граней и такой же комбинаторной окрестностью границы. В докладе будет рассказано, как при помощи таких операций построить любой фуллерен.
Торическая топология сопоставляет каждому простому n-мерному выпуклому многограннику с m гипергранями (m+n)-мерное момент-угол многообразие с действием m-мерого компактного тора T^m, пространство орбит которого совпадает с многогранником. Оказывается, многообразия, отвечающие фуллеренам, являются когомологически жёсткими: если градуированные кольца когомологий момент-угол многообразий двух трёхмерных многогранников, один из которых фуллерен, изоморфны, то многообразия эквивариантно диффеоморфны, а многогранники комбанаторно эквивалентны. Вторая часть доклада будет посвящена этому результату.

27.03 О честном делении и делении без зависти

Link to Zoom

Докладчик - Гаянэ Юрьевна Панина, ведущий научный сотрудник Факультета математики и компьютерных наук СПбГУ и Санкт-Петербургского отделения Математического института имени В. А. Стеклова РАН.

Представим себе, что r воров украли ожерелье с драгоценными камнями разных сортов и хотят поделить его, во-первых, честно (каждый сорт камней должен быть поделен строго поровну), а во-вторых, без зависти, то есть, с учетом индивидуальных предпочтений воров. Мы обсудим такие вопросы: каково минимальное число разрезов, гарантированно позволяющее такое деление? Можно ли при данном числе разрезов попросить вдобавок честность еще в каком-нибудь смысле?Как ни странно, этот круг задач решается исключительно топологическими методами. Здесь работают степень отображения, обобщение теоремы Борсука-Улама, теорема Брауэра, эквивариантные препятствия (впрочем, до препятствий дело не дойдет).

Гаянэ Юрьевна расскажет и историю задачи (работы N. Alon, D. Gale), и свою недавнюю совместную работу с D. Jojic и  R. Zivaljevic.

Для понимания доклада достаточно знать, что такое действие группы Z_n, симплициальный комплекс, связность.

20.03 Гиперболические нейронные сети

Докладчик - Максим Кочуров, студент 2 курса магистерской программы Сколтеха «Науки о данных»

В докладе будет рассмотрено применение гиперболической геометрии к задачам машинного обучения. Мы обсудим, когда от гиперболического пространства есть польза, когда нет, и как работать с ним в контексте нейронных сетей. Доклад будет охватывать такие задачи, как представления для графов, NLP, работа с изображениями. Будет приведен обзор статей и результатов, отвечающих на вопрос: когда и чем может быть полезна геометрия Лобачевского в машинном обучении.

13.03 Обзор методов оптимизации на многообразиях

Докладчик - Сергей Козлуков, студент 2 курса совместной магистерской программы Сколтеха и ВШЭ «Статистическая теория обучения»

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

Конкретно, кратко рассматривается Риманов градиентный спуск, обсуждается статья Octavian Ganea и Gary Becigneul, "Adaptive Riemannian Optimization Methods", обобщающая адаптивные схемы оптимизации на случай product manifold.

06.03 Теория вложенных графов в приложении к manifold learning

Докладчик - Максим Бекетов, выпускник МФТИ и Сколтеха, сотрудник Archeads Inc

Задача manifold learning состоит в том, чтобы, имея (достаточно большое) облако точек, сэмплированных с некоторого многообразия (вложенного в объемлющее пространство), восстановить это многообразие. Два самых популярных подхода к этой задаче – персистентные гомологии и анализ лапласианов графов – со своими преимуществами и недостатками, работают в общем случае. Докладчик расскажет про другой, недавний и довольно несложный подход, работающий в частном случае, когда искомое многообразие двумерно: вкратце, нужно приблизить плоскостями окрестности точек-представителей из данного облака и понять, как эти окрестности “склеены” между собой. В последнем нам помогут инструменты теории вложенных (в поверхности) графов, а именно rotation systems – циклические порядки вложений ребер, инцидентных вершине. Максим напомнит классификацию двумерных многообразий, а также геометрический смысл SVD-разложения, потому предварительных знаний не потребуется; и покажет результаты численных экспериментов авторов метода (код есть в открытом доступе).

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

28.02 Топологические методы в робототехнике: задачи и алгоритмы

Докладчик  - Анастасия Варава (Postdoctoral researcher) и Владислав Полянский (PhD student), KTH Royal Institute of Technology (Стокгольм, Швеция)

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

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

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

21.02 Магнитудные функции и магнитудные гомологии

Докладчик - Владислав Черепанов, аспирант мехмата МГУ, научный сотрудник лаборатории

 В докладе будет введено понятие магнитудной функции метрического пространства на основе работ Т.Лейнстера. Эта функция позволяет определить объем компактного подмножества евклидова пространства, а в случае графов - кодирует нетривиальную комбинаторную информацию. Будут сформулированы основные свойства магнитудных функций и разобраны показательные примеры, объясняющие, какие именно характеристики метрического пространства эти функции позволяют улавливать.

Далее будут определены магнитудные гомологии метрического пространства. Оказывается, что равенство нулю первых магнитудных гомологий является критерием выпуклости компакта в евклидовом пространстве. Определенная с помощью магнитудных гомологий эйлерова характеристика метрического пространства оказывается формально равна магнитудной функции. Таким образом, магнитудные гомологии можно рассматривать как категорификацию магнитудной функции. Если позволит время, разберем общее понятие магнитуды обогащенной категории и обсудим его свойства. 

13.02 Открытые задачи в песочных моделях

Докладчик - Никита Сергеевич Калинин, доцент департамента математики НИУ ВШЭ Санкт-Петербург, старший научный сотрудник Международной лаборатории теории игр и принятия решений

Рассмотрим граф, в каждой вершине которого находится целое неотрицательное число песчинок. Назовём обвалом следующую операцию: если в некоторой вершине число песчинок больше или равно её степени, переместим из этой вершины по одной песчинке в каждого из её соседей. Если граф конечный и связный, в нём есть стоки (то есть вершины, где попадающий туда песок исчезает), то любая последовательность обвалов приводит к стабильному состоянию системы: то есть к состоянию, где невозможно сделать обвал ни в одной вершине.

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

30.01 Метод Mapper как возможный подход к получению мультипараметрической устойчивости

Докладчик - Баларам Усов, студент математического факультета

Метод Mapper был предложен Гуннаром Карлссоном и другими исследователями [Gurjeet Singh, Facundo Mémoli, Gunnar Carlsson, 2007] как способ низкоразмерного представления данных. Идея Mapper-а довольно прямолинейна и отсылает к простым классическим топологическим конструкциям, но, несмотря на это, метод оказался довольно успешным и нашел применение в массе разных интересных приложений. Тем не менее, сами создатели указывают, что Mapper является довольно сподручным (ad-hoc) средством репрезентации данных и не годится как самостоятельный инструмент для понижения размерности. Докладчик планирует рассказать содержание алгоритма, некоторые детали его реализации, продемонстрировав его работу на нескольких датасетах. После этого планируется обсудить как из репрезентаций данных, получаемых Mapper-ом довольно естественно, возникают мультифильтрации на комплексе Вьеториса-Рипса. Оставшееся время будет посвящено рассказу про устойчивые гомологии таких мультифильтраций [Heather Harrington, Nina Otter, Hal Schenk, Ulrike Tillmann, 2019], а также про то, как они могут возникнуть в недавно изобретенной архитектуре топологических автоэнкодеров [Michael Moor, Max Horn, Bastian Rieck, Karsten Borgwardt, 2019]. Хотя пока это лишь идея, есть надежда, что Mapper может найти новое неожиданное применение.