PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Approximation and the Arity Barrier at Width Two

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

arXiv:2609.37417v1cs.CC

TL;DR

The paper asks whether robust approximation can remain independent of arity beyond width one, given the finite-language bounded-width characterization. It combines degree-eight SoS rounding with exact rational optimization and shows an arity-dependent upper bound matched by UGC hardness in a parameter regime.

  • Problem

    The bounded-width characterization for finite constraint languages fixes each relation's arity, leaving open whether robustness is uniform for constraints of unbounded arity.

    Source: §1 · p. 3

  • Method

    The paper rounds an exactly computed degree-eight SoS relaxation with a single Gaussian threshold and establishes rational fixed-degree optimization using truncated Gröbner bases.

    Source: §1 · pp. 4–5

  • Results

    For Majority-closed Boolean linear constraints, the randomized algorithm has expected loss O(√ε log k), and under UGC a matching dependence on deficit and arity is hard in a common parameter range.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Under UGC, arity-independent robust approximation does not extend uniformly to the width-two class, although the guarantee tends to zero with ε at each fixed arity.

    Source: §1 · p. 3

    UGC yields NP-hard promise distinctions; excluding randomized algorithms additionally uses NP ⊄ BPP, and the paper does not claim deterministic derandomization.

    Source: §6.5 · p. 20

Abstract

from arXiv · show

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 $\Omega(\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.

1 Introduction

The paper asks whether bounded width guarantees robust approximation uniformly when constraint arity is unbounded, and finds that it fails already for width-two Boolean linear constraints closed under Majority.

1 Introduction

  • The width-two class consists of Boolean linear relations preserved by coordinatewise Majority; their unary and binary projections determine each relation, and feasibility reduces to 2-SAT.The paper uses relational width (2, 3), with consistency on pairs extended through triples deciding feasibility.Source: §1 · p. 3
  • For Majority-closed Boolean linear constraints of maximum arity k ≥ 2, a randomized polynomial-time algorithm achieves expected loss O(√ε log k) on (1−ε)-satisfiable instances without knowing ε.It returns a satisfying assignment on satisfiable instances and runs in time polynomial in the binary encoding of rational rows and weights.Source: §1 · p. 4
  • Under UGC, the lower bound matches the upper bound in its dependence on deficit and arity in their common parameter range.The hardness construction gives finite rationally weighted instances and separated promise thresholds; the constants are not optimized.Source: §1 · p. 4
  • Under UGC, choosing k = 1 + ⌊e^2/ε⌋ makes it hard to achieve satisfiability above 1 − 5/64 on (1−ε)-satisfiable instances for fixed 0 < ε ≤ 1/20.For every fixed k, the upper bound still tends to zero with ε, so this barrier concerns uniformity over arities.Source: §1 · p. 4
  • The rounding uses degree-eight SoS and a single Gaussian threshold; conditioning on a row-conflict star's center controls its conflicts jointly and yields the √log k factor.Unary and binary obstructions receive pseudoexpectation at most the row deficit after strongly biased literals are separated.Source: §1 · p. 4
  • The computational result addresses a limitation of polynomial-size SoS relaxations: polynomial matrix dimension alone does not ensure polynomial bit complexity.The construction supplies complete truncated reduced Gröbner bases and rational bases of truncated vanishing identities.Source: §1 · pp. 4–5
  • At every fixed moment degree 2d, the relaxation admits polynomial-time rational optimization to any positive rational accuracy while remaining exactly feasible.Degree-2d SoS proofs can be found after additive perturbation at degree at most 4d + 10.Source: §1 · p. 5
  • The paper concludes that width alone does not control robust approximation uniformly over unbounded-arity relations, despite the width-one precedent and fixed-template characterization.The matching UGC lower bound shows that the arity dependence is unavoidable under the stated hardness assumptions.Source: §1 · pp. 3, 5

2 Soft Majority systems and conventions

This section specifies the Boolean linear constraint model, its soft-system encoding, and the algebraic conventions used for the SoS analysis.

2 Soft Majority systems and conventions

  • A Boolean relation is Majority-closed when it contains the coordinatewise majority of every triple of its members; each input row is a rational linear inequality whose Boolean solution set is Majority-closed.The input has nonnegative rational row weights normalized to sum to one, and arity is unrestricted.Source: §2 · p. 6
  • The soft system adds indicator variables and a nonnegative big-M condition so an inactive row is valid throughout the Boolean cube; setting each indicator to its satisfaction value recovers the integral objective.The soft feasible set is nonempty because setting all indicators to zero is feasible, and no additional coupling constraints are imposed.Source: §2 · p. 6
  • The rational vanishing ideal consists of rational polynomials that vanish on the specified Boolean set, with truncated basis elements selected by degree under the fixed graded lexicographic order.The text distinguishes this from running Buchberger's algorithm only up to a degree bound.Source: §2 · pp. 6–7
  • A degree-D SoS proof certifies nonnegativity through an identity using sums of squares and ideal multipliers, with rational positive-semidefinite Gram matrices as certificates.The stated certificates can also be expressed as sums of squares of rational polynomials.Source: §2 · p. 7

3 From rational moment optimization to robust approximation

This section connects exact rational optimization of the degree-eight soft-system relaxation to the robust-approximation algorithm, then describes the moment-deficit analysis and its scope.

3 From rational moment optimization to robust approximation

  • The weighted soft objective has integral optimum equal to the instance's integral value, by setting each row indicator to its satisfaction indicator.A general soft-feasible point may set an indicator to zero even when its row is satisfied.Source: §3 · p. 7
  • The degree-eight moment body imposes positivity on squares through degree four and on row-localizing products through degree eight.Its moment matrix has order four, and each nonconstant linear row has a localizing matrix of order three.Source: §3 · p. 7
  • For rational η > 0, the computational input theorem provides a polynomial-time Turing algorithm to compute an exactly feasible rational degree-eight pseudoexpectation.This supplies the degree-eight moments used by the rounding analysis.Source: §3 · p. 7

Its deficits satisfy

  • The deficit argument invokes positivity on squared indicator terms and Boolean identities to establish its bounds.The computed functional lies in S8, the moment body used by the rounding analysis; η affects the objective, while feasibility remains exact.Source: Its deficits satisfy · p. 8
  • The algorithm optimizes over K8, not S26, and does not assert that its computed moments extend to that higher-level body.The text states this higher-level optimization or extension is unnecessary for the rounding analysis.Source: Its deficits satisfy · p. 8

4 Literal normalization and low-degree penalties

Majority-closed linear rows can be represented by unary and binary obstructions, and degree-eight pseudoexpectations bound each such obstruction by the row deficit. These properties give a low-degree basis for the rounding analysis.

4.1 Unary obstructions and binary conflicts

  • Each row has at most one literal occurrence per variable, and its conflict graph joins pairs whose coefficients sum to more than T_j.A triangle-free induced conflict graph is a star with possible isolated vertices.Source: §4.1 · pp. 8–9
  • A Majority-closed row is satisfied exactly when every forbidden singleton or pair contains a false literal.Rows with T_j < 0 are empty, and the obstruction descriptions can be constructed in polynomial bit time.Source: §4.1 · pp. 8–9

4.2 Penalties from the original soft inequalities

  • The degree-eight penalty lemma bounds the pseudoexpectation of every forbidden singleton or pair by the row deficit.An identically false row has deficit 1.Source: §4.2 · p. 9
  • The penalty proof uses localized soft inequalities and squares of degree at most eight, with Boolean reductions not increasing the degree bounds.The localized term and positivity of the squares force the pseudoexpectation of the forbidden set indicator to zero.Source: §4.2 · p. 9

5 Gaussian threshold rounding with logarithmic arity dependence

The section rounds a degree-eight feasible functional using one Gaussian threshold, then jointly bounds conflicts within each row. It gives a uniform polynomial-time guarantee and compares the arity dependence with fixed-template results.

5.1 The global rounding rule

  • The rounding draws one standard Gaussian vector and thresholds scores at a scale s chosen from the deficit tolerance Δ and an arity-dependent H.The stated choice has Δ/(512H) < s^2 ≤ Δ/(128H), with log(ek) ≤ H ≤ 2 log(ek).Source: §5.1 · p. 10

5.3 Finite precision and a polynomial-time algorithm

  • The finite-precision implementation has polynomial time and random-bit use in the input size and tolerances.For dyadic ν, the precision dependence is polynomial in log2(1/ν) + 1.Source: §5.3 · p. 13
  • Theorem 5.4 guarantees expected-loss control when OPTint ≥ 1 − ε without requiring ε, and returns a satisfying assignment when positive-weight rows are satisfiable.The theorem states a uniform robust approximation guarantee for rational weighted Majority-closed Boolean linear systems.Source: §5.3 · p. 14

5.4 Comparison with fixed-template Majority rounding

  • Fixed-template Majority rounding gives OΓ(√ε), while this result exposes arity dependence for input relations; a union bound over forbidden outputs does not give the best arity dependency.The fixed-template constants may depend on the template, whereas this work gives explicit dependence on k.Source: §5.4 · p. 15

5.2 A joint estimate for all conflicts of a row

  • After excluding strongly biased literals, the retained conflict graph is a star, letting one Gaussian window control all edge conflicts jointly rather than using a union bound.Conditioning on the Gaussian component orthogonal to the center lets the weakest upper bound control the center score.Source: §5.2 · p. 11, §5.4 · p. 15

6 Gaussian gaps and UGC hardness

The section builds a finite basic-SDP gap from a Gaussian star, then uses UGC to establish hardness for Majority-closed Boolean linear constraints. The resulting hardness rules out an arity-independent robust guarantee under the stated assumptions.

6.1 The basic SDP and the gap-to-hardness theorem

  • For a fixed finite predicate language, a basic-SDP value at least c and integral value at most s < c yield UGC-hardness of distinguishing thresholds within additive slack ξ.The slack must satisfy 0 < ξ < (c − s)/2.Source: §6.1 · p. 16

6.2 An ideal Gaussian star

  • The Gaussian-star analysis gives failure greater than σ/5 for the paired predicates, using the exchangeable-Gaussians theorem to bound joint leaf membership.The theorem states that parallel halfspaces maximize simultaneous membership probability for exchangeable Gaussians with nonnegative common covariance.Source: §6.2 · pp. 16–17

6.3 Finite scopes and rational weights

  • Finite scopes approximate the Gaussian star correlations and retain an integral-value upper bound of 1 − σ/10 + ω.The construction has arity at most q + 1 and rational weights.Source: §6.3 · p. 17

6.4 A feasible solution of the full basic SDP

  • The star construction supplies a feasible full basic SDP solution while bounding each predicate's violation probability by 9ρ^2/8.The local distributions and Gram matrix establish global SDP feasibility.Source: §6.4 · p. 19

6.5 Separated hardness thresholds and the arity barrier

  • For every fixed 0 < ε ≤ 1/20, UGC makes it NP-hard to find an assignment satisfying more than 1 − 5/64 of the rows when arity is at most 1 + ⌊e^(2/ε)⌋.Assuming also NP ⊄ BPP, this rules out an arity-independent randomized polynomial-time robust guarantee over all arities.Source: §6.5 · p. 20

7 The combined computational and approximation theorem

The combined theorem establishes polynomial-time SoS tractability and a Gaussian-threshold approximation bound for Majority-closed Boolean linear systems. Under UGC, its arity-dependent error is optimal up to universal factors in the stated regime.

The combined computational and approximation theorem

  • For every fixed d, the truncated basis and identities are constructible in polynomial bit time, and exact-feasible rational points optimize K_2d to any rational accuracy.A degree-2d proof can be found after adding α at degree at most 4d + 10.Source: §7 · p. 21
  • Optimizing K8 and Gaussian-threshold rounding give the randomized polynomial-time upper bound, with satisfiable instances solved exactly and no assumption required.The upper bound is unconditional.Source: §7 · p. 21
  • Under UGC, the hardness and upper bounds match in order for k ≥ 21 in the stated regime; no equality of leading constants is asserted.Assuming also NP ⊄ BPP, there is no randomized polynomial-time arity-independent robust guarantee over all arities.Source: §7 · p. 21

8 Hard Majority relations: a complete basis construction

Majority-closed Boolean relations are determined by unary and binary projections, enabling polynomial-time 2-SAT feasibility and a compact reduced-basis construction. The hard relation's basis has at most 2n + n^2 + 1 elements.

Hard Majority relations: a complete basis construction

  • A nonempty Majority-closed Boolean relation is determined by its unary and binary projections and is expressible by clauses forbidding nonextendible partial assignments of size at most two.Feasibility and extendibility of assignments to at most two variables are decidable in polynomial time.Source: §8 · p. 22
  • For a 2-CNF solution set, the reduced graded lexicographic basis is computable in polynomial time and contains at most 2n + n^2 + 1 elements.Its elements lie in the stated Boolean, conflict, linear, and zero-polynomial families.Source: §8 · p. 23
  • The construction identifies forced values and equal-or-complementary variables, selects representatives, and encodes each remaining coordinate pair only for its unique forbidden assignment, if any.It yields a monic, reduced list using O(n^2) 2-SAT tests, with coefficients only in {0, 1, −1}.Source: §8 · pp. 23–24

9 The soft basis: structure, completeness, and truncation

The soft Majority ideal has a constructible reduced basis obtained by filtering a structured candidate list. Its truncations can be computed directly, yielding complete identities through each fixed degree.

The soft basis: structure, completeness, and truncation

  • The reduced soft basis is obtained by retaining exactly the candidate elements whose leading monomials are minimal under divisibility.The basis construction handles shared row indicators in the soft system.Source: §9 · pp. 24–25
  • For every truncation degree t, the correct truncated basis is computable in time polynomial in W_t and the input length, with at most W_t elements.Its coefficients are in {0, 1, −1}, and each element has at most four terms.Source: §9 · p. 24
  • The construction proves the candidate list generates the full vanishing ideal and filters it to a reduced basis, rather than relying on a degree cutoff of intermediate computations.The truncation procedure enumerates only candidates within the requested degree and applies a divisibility filter.Source: §9 · pp. 24–25
  • Boolean reduction alone does not preserve the structured families for arbitrary S-polynomials, so it cannot justify closure or the correct reduced-basis truncation.The construction instead reasons directly with the full vanishing ideal.Source: §9 · p. 25

10 Exact two-sided SoS derivations

The section replaces failed scalar refutations with degree-bounded SoS certificates, then lifts them to two-sided derivations for the soft system. It makes these constructions explicit and polynomial in bit complexity.

10.1 Why scalar Farkas multipliers do not suffice

  • Scalar Farkas multipliers cannot refute the four-row Boolean-infeasible example, but polynomial square multipliers and Boolean equations yield an exact degree-three SoS refutation.The LP relaxation contains (1/2, 1/2), where every row is zero.Source: §10.1 · p. 26

10.2 Extracting clauses from a rational linear row

  • Clause extraction from rational linear rows retains nonnegative slack terms, yielding refutations for binary, unary, and wholly infeasible rows at degrees at most six, four, and two, respectively.For a binary forbidden assignment, the three term types have degrees four, five, and six.Source: §10.2 · p. 26

10.3 Implication paths and a degree-eight hard refutation

  • Every infeasible rational system of Majority-closed Boolean linear rows has a constructible rational degree-eight SoS refutation.Extracted clauses give implication paths whose differences telescope to a Boolean refutation.Source: §10.3 · pp. 26–27

10.4 Conditioning and lifting by squared activation indicators

  • For each specified vanishing-basis element, both signs have rational SoS certificates from the original soft system, with degree at most 2 deg p + 10.The construction conditions on assignments to at most two variables and lifts restricted refutations using squared activation indicators.Source: §10.4 · p. 27
  • The table records formal certificate degrees before Boolean reduction, while the lifted degree bound depends on the conditioned-variable count and the support size.The stated free-term degree is 2|K| + 2r + 8.Source: §10.4 · pp. 27–28, Table 1 · p. 28

10.5 Explicit ideal multipliers and binary encoding

  • Explicit ideal multipliers turn the congruences into exact certificates using only the original inequalities, with no auxiliary clause, hard-row, or fixing axioms.The construction has polynomial bit complexity; a positive extraction gap remains manageable even when very small.Source: §10.5 · pp. 28–29

11 The general criteria in the form used here

The section states the general dual and transfer criteria used in the paper. Together, they support perturbed rational proof search and bound the cost of removing added identities.

Dual criterion

  • Given the stated boundedness and proof-existence conditions, the dual criterion permits polynomial-time rational search for a certificate of f + η ≥ 0 at an even degree O(d).The resulting perturbed certificate is an exact polynomial identity.Source: §11 · p. 29

Transfer

  • A proof using added equality axioms transfers to the original system when both signs of each added polynomial have proofs there, with degree determined by their certificate bounds.The transfer preserves rationality and has polynomial bit cost.Source: §11 · pp. 29–30

Degree bound and scope

  • Using the per-element degree bound gives a transfer and search ceiling of 4d + 10; the section does not claim rational unperturbed proofs or search at degree 2d.The bound follows from Db + 2(2d − deg b) ≤ 4d + 10.Source: §11 · p. 30

12 Primal optimization with the computed basis

The section constructs complete low-degree identities and affine coordinates for the soft system, then combines them with dual transfer criteria. This yields exact rational moment feasibility and a one-sided comparison with a higher relaxation level.

12 Primal optimization with the computed basis

  • The primal optimization uses a strengthened moment body that annihilates every vanishing identity through degree r.Its defining moments satisfy normalization and Boolean multilinearization constraints.Source: §12 · p. 30

12.1 Main primal-dual tractability theorem

  • The computed basis and two-sided derivations support rational optimization with exact normalization, equality, and PSD constraints at the stated moment degree.The complete basis is computed in polynomial time, and the optimized moments remain degree 2d.Source: LG. Filter it to Gr. The list · p. 31, §12.1 · pp. 32–33

LG. Filter it to Gr. The list

  • At fixed moment degree r, a complete rational basis of truncated vanishing identities and its normal-form table are computable in polynomial bit time.The standard-monomial coordinates give a rational affine parametrization, without enumerating the feasible set.Source: LG. Filter it to Gr. The list · p. 31

12.1 Main primal-dual tractability theorem

  • The resulting rational pseudoexpectation is exactly feasible in K2d, with the stated one-sided comparison to level 4d + 10.For maximization, its objective is at least the level-4d+10 optimum minus η.Source: §12.1 · p. 32
  • The result does not assert K2d = S2d or extendibility of the computed point to S4d+10; only the stated one-sided objective comparison is guaranteed.Proof search perturbs the objective by η, whereas primal feasibility is exact.Source: §12.1 · p. 33
Loading 2609.37417v1…