Topic: Гипотеза Борсука, задачи о справедливом дележе, быстрые алгоритмы и приложения комбинаторной топологии.
В рамках доклада будут даны не только сведения о уже полученных результатах но и даны необходимые preliminaries для двух задач, про которые предлагается подумать о возможности получения решений через AI. (В духе того, что будет показано на первой паре)
Анонс от автора доклада:
Знаменитая гипотеза Борсука неверна для n ⩾ 64, вопрос остаётся открытым для 4 ⩽ n ⩽ 63. Пример для n=64 был построен для множества с двумя расстояниями. Я опишу метод построения таких множеств из произвольного графа и обсужу возможность построения контрпримеров с помощью нейронных сетей.
Задача о справедливом дележе стара и известна, имеет множество форм и встречается во многих реальных ситуациях. В этом докладе я рассмотрю теоремы существования для задач о гармонии арендной платы и разрезании торта, а также их обобщения.
Третья часть доклада была вдохновлена статьей в New York Times “To Divide the Rent, Start With a Triangle” by Albert Sun (April 28, 2014), которая содержит калькулятор справедливой арендной платы, основанный на работе Фрэнсиса Су. Мы рассматриваем алгоритмическую сложность задач о справедливом дележе, уделяя особое внимание минимизации количества запросов, необходимых для нахождения приближенного решения с желаемой точностью. Для нескольких классов задач о справедливом дележе показано, что при определенных естественных условиях на множествах предпочтений логарифмическое количество запросов относительно точности достаточно.
Недавние исследования показали, что сложность нейронной сети тесно связана с топологической сложностью её входных данных. В связи с этим, мы предлагаем новый, основанный на топологии подход «разделяй и властвуй», основанный на разложении входных данных на топологически более простые подмножества. Наш метод разбивает набор данных на сбалансированные области, используя теорему о сэндвиче с ветчиной, и направлен на минимизацию топологической сложности.
Я также рассмотрю некоторые другие проблемы, связанные с применением комбинаторной топологии
Это будет на паре 14.10.25 в 18 00 также в аудитории 108 и также, по очевидным причинам, докладчик будет присутствовать онлайн, однако, всех кто придет на матфак будем очень рады видеть