arXiv · 03.08.2026 ·Исследования и наука

Новые результаты в теории сложности булевых функций и коммуникационной сложности

Исследователи представили конструкцию однозначных дизъюнктивных нормальных форм (DNF) с шириной O(n) и сложностью 0-сертификатов Ω(n²). Используя структуру этих формул, авторы доказали теорему о подъеме (lifting theorem) с константным гаджетом. Это позволило перенести разделение в сложности сертификатов на коммуникационную сложность, что привело к оптимальному опровержению гипотезы Алона-Сакса-Сеймура в контексте коммуникационных задач.

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

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

Ключевые факты

Построены однозначные DNF с шириной O(n) и сложностью 0-сертификатов Ω(n²).
Доказана теорема о подъеме с константным гаджетом для коммуникационных проблем.
Результат обеспечивает оптимальное опровержение гипотезы Алона-Сакса-Сеймура.
Исследование опирается на методы комбинаторной теории сложности и коммуникационной сложности.

Источник: arXiv

Обсудить с ИИ

Похожие материалы

arXiv · Исследования и наука Новый подход к формальному доказательству теорем с помощью диффузионных моделей Исследователи представили метод Diffusion-Proof, направленный на преодоление ограничений стандартных авторегрессионных языковых моделей в задачах формальной математики. Традиционные модели, предсказывающие следующий токен, часто сталкиваются с трудностями при построении длинных логических цепочек, необходимых для верификации сложных математических доказательств. Новый подход переносит принципы диффузионных процессов в область формального вывода, позволяя моделям более эффективно исследовать пространство возможных доказательств. Hacker News · Исследования и наука ИИ помог решить 30-летнюю математическую задачу в области выпуклой оптимизации Исследователи применили продвинутую языковую модель для решения давней математической проблемы, связанной с гипотезой о выпуклой оптимизации. ИИ удалось найти доказательство, которое оставалось недоступным для математиков на протяжении трех десятилетий. Этот прорыв демонстрирует способность нейросетей не просто генерировать текст, но и выполнять сложные логические выводы в фундаментальных научных дисциплинах, требующих строгой формализации. arXiv · Машинное обучение Математическое доказательство барьера сложности в разреженных методах наименьших квадратов Исследователи подтвердили гипотезу о фундаментальном ограничении сложности для алгоритмов разреженной выпуклой оптимизации. Работа доказывает, что линейная зависимость от ограниченного числа обусловленности в задачах наименьших квадратов является неустранимым барьером для любых полиномиальных алгоритмов. Результат опирается на гипотезу о расширении малых множеств (Small-Set Expansion Hypothesis), что закрывает давний теоретический вопрос в области вычислительной сложности. arXiv · Машинное обучение Новые законы больших чисел для липшицевых функций в машинном обучении Исследователи представили доказательство сильных законов больших чисел для локально липшицевых функций в липшицевой псевдометрике. Работа расширяет теоретическую базу для анализа сходимости в сложных моделях, включая функции, определимые в о-минимальных структурах. Полученные результаты обеспечивают строгие гарантии равномерной сходимости для лимитирующих и субдифференциалов Кларка, что критически важно для оптимизации нейронных сетей. arXiv · Исследования и наука Новые теоретические границы для задачи мульти-секретаря Исследователи представили работу, устанавливающую строгие нижние границы для аддитивного сожаления (regret) в задаче мульти-секретаря. Авторы доказали, что для распределений с разрывами в поддержке достижение границы O(log T) невозможно, что закрывает давний вопрос о сложности алгоритмов принятия решений в условиях неопределенности и ограниченной информации при выборе оптимальной стратегии. arXiv · Машинное обучение Новый метод анализа сходимости алгоритмов оптимизации через контактные гамильтоновы системы Исследователи предложили новый математический подход для анализа дискретных алгоритмов оптимизации, используя контактные гамильтоновы системы. Метод позволяет переносить сертификаты сходимости из непрерывных дифференциальных уравнений на дискретные итерационные процессы. Это решает фундаментальную проблему разрыва между теоретической динамикой и практической реализацией алгоритмов, обеспечивая более точные гарантии скорости сходимости при геометрическом убывании целевых функций. arXiv · Исследования и наука Новое исследование объясняет превосходство нейросетей над NTK в задачах с композиционной структурой Исследователи представили математическое обоснование того, почему современные нейронные сети значительно превосходят предел нейронного касательного ядра (NTK) при решении задач с композиционной структурой. Авторы работы ввели дихотомию между двумя мерами сложности целевой функции, доказав, что NTK демонстрирует экспоненциальную субоптимальность в случаях, когда данные обладают иерархической или композиционной природой, что ранее наблюдалось лишь эмпирически. arXiv · Исследования и наука Новая алгебраическая теория вычислительных способностей трансформеров Исследователи представили формальную теорию, описывающую вычислительные возможности трансформеров с причинно-следственной маскировкой (causally masked) в условиях ограниченной точности вычислений. Авторы доказывают, что при конечном представлении чисел порядок операций и ошибки округления критически влияют на то, какую информацию механизм внимания способен сохранять и обрабатывать, что ограничивает или расширяет спектр решаемых моделью задач для произвольной длины входных данных. arXiv · Исследования и наука Математическое обоснование сходимости алгоритмов DGM и PINN для решения нелинейных уравнений Исследователи представили доказательство глобальной сходимости методов Deep Galerkin Method (DGM) и Physics Informed Neural Networks (PINNs) при решении нелинейных дифференциальных уравнений в частных производных. Работа устраняет теоретический пробел в области научного машинного обучения, подтверждая надежность нейросетевых аппроксимаций, которые ранее использовались преимущественно на эмпирическом уровне для моделирования сложных физических процессов. arXiv · Машинное обучение Применение глубокого обучения для подавления помех в OFDM-системах Исследователи представили новый метод борьбы с узкополосными помехами (NBI) в системах мультиплексирования с ортогональным частотным разделением каналов (OFDM) с помощью глубокого обучения. Подход заменяет традиционные методы сжатого зондирования, устраняя их высокую задержку и проблемы с нелинейными искажениями, что значительно повышает точность мягкой демодуляции и общую надежность передачи данных в условиях зашумленного радиоэфира.

← Все материалы