Limitations found in robust approximation for constraints with many variables

Robust Approximation and the Arity Barrier at Width Two

Computational Complexity

Summary

The paper studies how well certain mathematical problems with many conditions can be approximated when they are mostly but not completely possible to solve. It shows that while earlier work found good approximation methods that work regardless of how many variables the problem has, this no longer holds true when problems have a certain structural complexity called width two. The authors provide an algorithm that works well up to a certain error margin but prove that improving this significantly is impossible under a major theoretical assumption. They also develop new mathematical tools to solve these problems more reliably and precisely.

What this means in practice

A theory result. No direct application yet.

Authors

Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli

Abstract

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.