pith. sign in

arxiv: 2605.10010 · v1 · submitted 2026-05-11 · 💻 cs.CC

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Amey Bhangale , Yezhou Zhang This is my paper

Pith reviewed 2026-05-12 03:19 UTC · model grok-4.3

classification 💻 cs.CC
keywords constraint satisfaction problemsapproximation algorithmsinapproximabilityfinite groupslinear equationsapproximation resistancesatisfiability
0
0 comments X

The pith

For certain S in a finite group G, the generalized linear equation CSP admits an optimal approximation algorithm on satisfiable instances assuming P is not NP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines constraint satisfaction problems whose constraints require that a group operation applied to the values of the involved variables lands in a fixed subset S of the group G. It constructs an approximation algorithm that works when every constraint can be satisfied simultaneously. For particular choices of G and S, the ratio achieved by this algorithm is proven optimal, assuming P does not equal NP. The same predicates are already known to resist nontrivial approximation when only almost all constraints need to be satisfied, creating a sharp distinction between the two regimes.

Core claim

We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain S assuming P≠NP. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming P≠NP, but admits a non-trivial approximation algorithm on satisfiable instances.

What carries the argument

The generalized linear equation predicate over finite group G with subset S, which requires the group operation on the assigned values to yield an element of S.

If this is right

  • The given algorithm achieves the best possible approximation ratio on satisfiable instances for the relevant S.
  • No polynomial-time algorithm can improve on this ratio for those S unless P equals NP.
  • The same predicates remain approximation resistant when the instance is only almost satisfiable.
  • This supplies a rare explicit example of a predicate whose approximability changes qualitatively once perfect satisfaction is required.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation hints that perfect satisfiability can sometimes be exploited to obtain approximation guarantees unavailable in the almost-satisfiable regime.
  • Analogous distinctions between satisfiable and almost-satisfiable approximability may appear in other algebraic or group-based CSPs.
  • The technique of tailoring algorithms specifically to fully satisfiable instances could be tested on additional predicates that are currently known only to be hard in the almost-satisfiable setting.

Load-bearing premise

That P is not equal to NP and that the chosen finite group G and subset S possess the algebraic properties that make the optimality and resistance proofs go through.

What would settle it

A polynomial-time algorithm that obtains a strictly better approximation ratio than the given one on satisfiable instances for any of the specific S where optimality is claimed would refute the result.

read the original abstract

Constraint satisfaction problems (CSPs) consist of a set of variables taking values from some finite domain and a set of local constraints on these variables. The objective is to find an assignment to the variables that maximizes the fraction of satisfied constraints. In this work, we study the CSP where the constraints are generalized linear equations over a finite group G. More specifically, for a given $S \subseteq G$, the constraints in this CSP are of the form addition of the values to the variables (similarly, product for non-abelian groups), belonging to the set $S$. We give an approximation algorithm for this problem on satisfiable instances and show that it is optimal for certain $S$ assuming $P\neq NP$. This natural predicate is one of the very few known predicates that are approximation resistant on almost satisfiable instances, assuming $P\neq NP$, but admits a non-trivial approximation algorithm on satisfiable instances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies constraint satisfaction problems (CSPs) in which constraints are generalized linear equations over a finite group G: for a fixed subset S ⊆ G the constraints require that the group operation (sum or product) applied to the values of the variables lies in S. The authors present a polynomial-time approximation algorithm that achieves a ratio strictly better than random assignment on fully satisfiable instances and prove that, for certain choices of S, this ratio is optimal under P ≠ NP because the problem is approximation-resistant even on (1−ε)-satisfiable instances.

Significance. If the stated algorithmic guarantee and matching hardness hold, the result is significant: it supplies one of the very few natural predicates known to be approximation-resistant on almost-satisfiable instances while still admitting a non-trivial approximation algorithm on fully satisfiable instances. The work therefore sharpens the boundary between approximability and inapproximability for group-based CSPs and supplies both an explicit algorithm and algebraic conditions on S that make the two directions tight.

minor comments (3)
  1. The abstract and introduction refer to “certain S” without stating the precise algebraic conditions on S (e.g., the subgroup or coset properties) that simultaneously enable the algorithm and the hardness; these conditions should be stated explicitly in the first section that introduces the predicate.
  2. The manuscript should include a short comparison, perhaps in the introduction or a dedicated subsection, with the handful of other predicates known to exhibit the same “resistant on almost-sat, approximable on sat” behavior, citing the relevant prior works.
  3. Notation for the non-abelian case (product instead of sum) is introduced only briefly; a short paragraph clarifying how the algorithm and reduction extend verbatim to the non-abelian setting would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. We appreciate the recognition that the result sharpens the boundary between approximability and inapproximability for this class of group-based CSPs.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes an approximation algorithm for satisfiable instances of the generalized linear equations CSP over finite group G with predicate S, together with a matching inapproximability result on almost-satisfiable instances under P≠NP for specific algebraic choices of S. Both the algorithmic guarantee and the hardness reduction are derived from the group structure and standard PCP-based techniques; neither reduces to a fitted parameter, self-definition, or self-citation chain that would make the claimed ratio equivalent to its inputs by construction. The algebraic conditions on S are stated explicitly as the precise requirements that simultaneously enable the non-trivial approximation on fully satisfiable instances and the resistance on (1-ε)-satisfiable instances, with no renaming of known results or smuggling of ansatzes via prior self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no explicit free parameters, axioms, or invented entities are stated. The result relies on the standard assumption P ≠ NP and unspecified algebraic conditions on G and S.

pith-pipeline@v0.9.0 · 5455 in / 1085 out tokens · 53217 ms · 2026-05-12T03:19:16.830090+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

  1. [1]

    Journal of the ACM (JACM) , volume=

    Proof verification and the hardness of approximation problems , author=. Journal of the ACM (JACM) , volume=. 1998 , address =

    work page 1998

  2. [2]

    Probabilistic checking of proofs: A new characterization of

    Arora, Sanjeev and Safra, Shmuel , journal=. Probabilistic checking of proofs: A new characterization of. 1998 , address =

    work page 1998

  3. [3]

    Journal of the ACM (JACM) , volume=

    Some optimal inapproximability results , author=. Journal of the ACM (JACM) , volume=. 2001 , address =

    work page 2001

  4. [4]

    Random Structures & Algorithms , volume=

    Three-query PCPs with perfect completeness over non-Boolean domains , author=. Random Structures & Algorithms , volume=. 2005 , publisher =

    work page 2005

  5. [5]

    Conditional hardness of approximating satisfiable

    Tang, Linqing , booktitle=. Conditional hardness of approximating satisfiable. 2009 , address =

    work page 2009

  6. [6]

    SIAM Journal on Computing , volume=

    A parallel repetition theorem , author=. SIAM Journal on Computing , volume=. 1998 , publisher=

    work page 1998

  7. [7]

    Theoretical Computer Science , volume=

    Inapproximability results for equations over finite groups , author=. Theoretical Computer Science , volume=. 2004 , publisher =

    work page 2004

  8. [8]

    Journal of the ACM (JACM) , volume=

    Feige, Uriel and Goldwasser, Shafi and Lov. Journal of the ACM (JACM) , volume=. 1996 , publisher =

    work page 1996

  9. [9]

    Journal of computer and system sciences , volume=

    Self-testing/correcting with applications to numerical problems , author=. Journal of computer and system sciences , volume=. 1993 , publisher=

    work page 1993

  10. [10]

    Geometric and Functional Analysis , volume=

    Gaussian bounds for noise correlation of functions , author=. Geometric and Functional Analysis , volume=. 2010 , publisher=

    work page 2010

  11. [11]

    Computational Complexity , volume=

    Approximation resistant predicates from pairwise independence , author=. Computational Complexity , volume=. 2009 , publisher=

    work page 2009

  12. [12]

    Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Product growth and mixing in finite groups , author=. Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2008 , publisher =

    work page 2008

  13. [13]

    Combinatorics, Probability and Computing , volume=

    Quasirandom Groups , author=. Combinatorics, Probability and Computing , volume=. 2008 , publisher=

    work page 2008

  14. [14]

    Information and Computation , volume=

    The complexity of solving equations over finite groups , author=. Information and Computation , volume=. 2002 , publisher=

    work page 2002

  15. [15]

    2009 , address =

    Computational complexity: a modern approach , author=. 2009 , address =

    work page 2009

  16. [16]

    1999 , address =

    Fourier analysis on finite groups and applications , author=. 1999 , address =

    work page 1999

  17. [17]

    Cambridge University Press, doi:10.1017/CBO9781139814782

    Analysis of boolean functions , author=. 2014 , address =. doi:https://doi.org/10.1017/CBO9781139814782 , publisher=

    work page doi:10.1017/cbo9781139814782 2014

  18. [18]

    ISBN 9781450380539

    Amey Bhangale and Subhash Khot , editor =. Optimal inapproximability of satisfiable k-LIN over non-abelian groups , booktitle =. 2021 , url =. doi:10.1145/3406325.3451003 , timestamp =

    work page doi:10.1145/3406325.3451003 2021

  19. [19]

    (updated paper) , year =

    Bhangale, Amey and Khot, Subhash , title =. (updated paper) , year =

    work page

  20. [20]

    SIAM Journal on Computing , title =

    H. SIAM Journal on Computing , title =. 2014 , number =. doi:10.1137/120882718 , publisher =

    work page doi:10.1137/120882718 2014

  21. [21]

    2022 , isbn =

    Bhangale, Amey and Khot, Subhash and Minzer, Dor , booktitle =. 2022 , address =. doi:10.1145/3519935.3520028 , isbn =

    work page doi:10.1145/3519935.3520028 2022

  22. [22]

    Balogh, D

    Bhangale, Amey and Khot, Subhash and Minzer, Dor , booktitle =. 2023 , address =. doi:10.1145/3564246.3585120 , isbn =

    work page doi:10.1145/3564246.3585120 2023

  23. [23]

    Balogh, D

    Amey Bhangale and Subhash Khot and Dor Minzer , booktitle =. On Approximability of Satisfiable k-CSPs:. 2023 , address =. doi:10.1145/3564246.3585121 , isbn =

    work page doi:10.1145/3564246.3585121 2023

  24. [24]

    On Approximability of Satisfiable k-CSPs: IV , year =

    Bhangale, Amey and Khot, Subhash and Minzer, Dor , booktitle =. On Approximability of Satisfiable k-CSPs: IV , year =. doi:10.1145/3618260.3649610 , isbn =

    work page doi:10.1145/3618260.3649610

  25. [25]

    Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More , booktitle =

    Amey Bhangale and Subhash Khot and Dor Minzer , editor =. On Approximability of Satisfiable k-CSPs:. Proceedings of the 57th Annual. 2025 , url =. doi:10.1145/3717823.3718127 , timestamp =

    work page doi:10.1145/3717823.3718127 2025

  26. [26]

    2009 , address =

    Chattopadhyay, Arkadev and Wigderson, Avi , booktitle =. 2009 , address =. doi:10.1109/FOCS.2009.17 , issn =

    work page doi:10.1109/focs.2009.17 2009

  27. [27]

    Approximation resistance from pairwise-independent subgroups , year =

    Chan, Siu On , journal =. Approximation resistance from pairwise-independent subgroups , year =. doi:10.1145/2873054 , numpages =

    work page doi:10.1145/2873054

  28. [28]

    Approximation resistance on satisfiable instances for predicates with few accepting inputs , year =

    Huang, Sangxia , booktitle =. Approximation resistance on satisfiable instances for predicates with few accepting inputs , year =. doi:10.4086/toc.2014.v010a014 , journal =

    work page doi:10.4086/toc.2014.v010a014 2014

  29. [29]

    Optimal algorithms and inapproximability results for every CSP? , year =

    Raghavendra, Prasad , booktitle =. Optimal algorithms and inapproximability results for every CSP? , year =

    work page

  30. [30]

    Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? , year =

    Khot, Subhash and Kindler, Guy and Mossel, Elchanan and O'Donnell, Ryan , journal =. Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? , year =. doi:10.1137/S0097539705447372 , publisher =

    work page doi:10.1137/s0097539705447372

  31. [31]

    32 Petra Schuurman and Gerhard J Woeginger

    Schaefer, Thomas J. , booktitle =. The Complexity of Satisfiability Problems , year =. doi:10.1145/800133.804350 , isbn =

    work page doi:10.1145/800133.804350

  32. [32]

    Monotone monadic

    Tom. Monotone monadic. Proceedings of the Twenty-Fifth Annual. 1993 , url =. doi:10.1145/167088.167245 , timestamp =

    work page doi:10.1145/167088.167245 1993

  33. [33]

    SIAM Journal on Computing , title =

    Feder, Tom. SIAM Journal on Computing , title =. 1998 , number =. doi:10.1137/S0097539794266766 , publisher =

    work page doi:10.1137/s0097539794266766 1998

  34. [34]

    37 Uri Zwick

    Zhuk, Dmitriy , journal =. A Proof of the CSP Dichotomy Conjecture , year =. doi:10.1145/3402029 , issue_date =

    work page doi:10.1145/3402029

  35. [35]

    , booktitle =

    Bulatov, Andrei A. , booktitle =. A Dichotomy Theorem for Nonuniform CSPs , year =

    work page

  36. [36]

    Hardness of Approximate Hypergraph Coloring , journal =

    Guruswami, Venkatesan and Hastad, Johan and Sudan, Madhu , journal =. Hardness of Approximate Hypergraph Coloring , year =. doi:10.1137/S0097539700377165 , publisher =

    work page doi:10.1137/s0097539700377165

  37. [37]

    Hardness results for approximate hypergraph coloring , year =

    Subhash Khot , booktitle =. Hardness results for approximate hypergraph coloring , year =. doi:10.1145/509907.509962 , isbn =

    work page doi:10.1145/509907.509962

  38. [38]

    Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs , year =

    Subhash Khot , booktitle =. Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs , year =

    work page

  39. [39]

    2013 , address =

    Dinur, Irit and Guruswami, Venkatesan , booktitle =. 2013 , address =

    work page 2013

  40. [40]

    A Two-Prover One-Round Game with Strong Soundness , year =

    Subhash Khot and Muli Safra , journal =. A Two-Prover One-Round Game with Strong Soundness , year =. doi:10.4086/toc.2013.v009a028 , publisher =

    work page doi:10.4086/toc.2013.v009a028 2013

  41. [41]

    SIAM Journal on Computing , title =

    Guruswami, Venkatesan and H. SIAM Journal on Computing , title =. 2011 , number =. doi:10.1137/090756144 , publisher =

    work page doi:10.1137/090756144 2011

  42. [42]

    Available: https://doi.org/10.1145/227683.227684

    Goemans, Michel X. and Williamson, David P. , journal =. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming , year =. doi:10.1145/227683.227684 , numpages =

    work page doi:10.1145/227683.227684

  43. [43]

    A PCP characterization of NP with optimal amortized query complexity , year =

    Samorodnitsky, Alex and Trevisan, Luca , booktitle =. A PCP characterization of NP with optimal amortized query complexity , year =. doi:10.1145/335305.335329 , isbn =

    work page doi:10.1145/335305.335329

  44. [44]

    Approximating np-hard problems efficient algorithms and their limits , year =

    Raghavendra, Prasad , school =. Approximating np-hard problems efficient algorithms and their limits , year =. doi:10.5555/1751149 , isbn =

    work page doi:10.5555/1751149

  45. [45]

    On Rich 2-to-1 Games , booktitle =

    Mark Braverman and Subhash Khot and Dor Minzer , editor =. On Rich 2-to-1 Games , booktitle =. 2021 , url =. doi:10.4230/LIPICS.ITCS.2021.27 , timestamp =

    work page doi:10.4230/lipics.itcs.2021.27 2021

  46. [46]

    On the power of unique 2-prover 1-round games , year =

    Khot, Subhash , booktitle =. On the power of unique 2-prover 1-round games , year =

    work page

  47. [47]

    Satisfying Degree- d Equations over GF[2]^n , year =

    H. Satisfying Degree- d Equations over GF[2]^n , year =. Theory of Computing , volume =. doi:10.4086/toc.2013.v009a027 , publisher =

    work page doi:10.4086/toc.2013.v009a027 2013

  48. [48]

    2003 , isbn =

    Dinur, Irit and Guruswami, Venkatesan and Khot, Subhash and Regev, Oded , title =. 2003 , isbn =. doi:10.1145/780542.780629 , booktitle =

    work page doi:10.1145/780542.780629 2003