О нулях и алгоритмах для неупорядоченных систем

Куикуи Лю (MIT) https://simons.berkeley.edu/talks/kui... Вероятностные явления на графах, группах и многообразиях Подсчет и выборка являются фундаментальными алгоритмическими примитивами в многомерной статистике и информатике. Для многих моделей существует огромная литература, изучающая вычислительную сложность этих задач в худшем случае и то, как они связаны с фазовыми переходами, которые претерпевает базовая система при изменении ее параметров (например, «температуры»). Их сложность в среднем случае изучена сравнительно меньше. Мы изучаем проблему оценки функции распределения моделей Изинга со случайными взаимодействиями. Это фундаментальные вероятностные распределения, возникшие в статистической физике, которые представляют собой полезную песочницу для новых алгоритмов и математических методов. Мы представляем первый алгоритм QPTAS для модели Шеррингтона-Киркпатрика и первый алгоритм FPTAS для антиферромагнитной модели Изинга на равномерно случайном d-регулярном графе для всех обратных температур вплоть до соответствующих порогов нарушения репликационной симметрии; считается, что за пределами этих порогов подобных алгоритмов не существует. Для достижения этих результатов мы изучаем расположение нулей функции распределения, черпая вдохновение из основополагающей программы Ли-Янга. Более конкретно, мы устанавливаем отсутствие нулей Фишера с помощью комбинации формулы Йенсена, метода второго момента и обусловливания малых подграфов. Совместная работа с Ференцем Бенчем, Брайсом Хуангом, Даниэлем З. Ли и Гусом Регтсом.