Приближенные гомоморфизмы алгебры функций на булевом кубе и алгоритмы сумм квадратов

Иерархия Лассера является одним из наиболее популярных подходов изучению точности аппроксимации для задач комбинаторной оптимизации. Основной сложностью в данном подходе является необходимость придумывать алгоритмы округления и оценивать их точность приближения, и желательно, чтобы существовал некоторый общий метод построения приближённых решений. В данной работе мы будем исследовать метод округления релаксаций Лассера для задач на булевом кубе, основанный на близости решений релаксаций ——- псевдораспределений на множестве допустимых решений исходной задачи ——- к гомоморфизмам алгебры функций. Мы изучим приближённые гомоморфизмы алгебры функций на булевом кубе ——- такие псевдораспределения, для которых гарантируется приближённое выполнение условий гомоморфизма, возможно лишь на каком-то подмножестве многочленов, установим, насколько близки подобные псевдораспределения к истинным гомоморфизмам. Кроме того, мы рассмотрим псевдораспределения, удовлетворяющие свойству приближённого гомоморфизма с некоторой вероятностью, а также возможные их приложения к улучшению существующей точности аппроксимации задачи MAX-CUT.