betaFeedback

WorksComputer Science

Abelian embeddings make useful promises: approximation of detrivialised equations

Abstract

We study the following family of search problems: given a system of equations x+y+z≡0(modp)x+y+z\equiv 0\pmod p promised to admit a solution that is nonconstant on every equation, find a cc-colouring of the variables that makes no equation monochromatic. For p∈{2,3}p\in\{2,3\}, the problem recovers known tractable Promise Constraint Satisfaction Problems (PCSPs). For p>3p > 3, we obtain a complete complexity classification: the problem is polynomial-time solvable for c≥4c \geq 4, yet even its decision version is NP-hard for c=3c = 3, and it is not well-defined for c=2c = 2. Our main conceptual contribution is a general tractability framework for PCSPs based on Abelian embeddings, a notion introduced by Bhangale, Khot, and Minzer [STOC 2022] in the study of quantitative approximation of satisfiable CSPs. We show that suitable Abelian embeddings yield polynomial-time PCSP reductions realised by singleton algorithms in the sense of Zhuk [FOCS 2026]. On the hardness side, the promise relation is far removed from the reconfigurable regime covered by the conditional hardness framework of Banakh, Barsukov, and Nakajima [LICS 2026]; our proof instead relies on a new additive-combinatorial rigidity theorem classifying special 33-colourings of Zp\mathbb{Z}_p.

Introduction

In a constraint satisfaction problem (CSP), variables take values in a fixed domain, and constraints specify which combinations of values are allowed. The task is to find an assignment that satisfies every constraint. Even when such an assignment is promised to exist, finding one can be computationally hard. This motivates studying approximation of satisfiable CSPs, where we relax the requirement either quantitatively or qualitatively. In quantitative approximation, we seek an assignment satisfying as many of the original constraints as possible. In qualitative approximation, we weaken the constraints and seek an assignment satisfying every weakened constraint. We illustrate this distinction with two examples of well-known NP-hard CSPs.

Given a graph promised to be 3-colourable, a quantitative approximation seeks an assignment of three colours that gives different colours to the endpoints of as many edges as possible. A randomised polynomial-time algorithm by Goemans and Williamson [27] based on semidefinite programming finds a 3-colouring that properly colours at least a 0.836 fraction of the edges in expectation. A qualitative approximation instead allows more colours—say, 100—while still requiring the endpoints of every edge to receive different colours. This problem was recently shown to be NP-hard [DMR09, GS20, FMW26].

In (monotone) 1-in-3-SAT, each clause requires exactly one of its three literals to be true. Given a satisfiable instance, quantitative approximation seeks an assignment satisfying as many clauses as possible. A qualitative approximation can instead weaken the requirement to Not-All-Equal: every clause must contain both a true and a false literal. This relaxation is solvable in polynomial time, as shown by Brakensiek and Guruswami [7]. Many other qualitative approximations of 1-in-3-SAT have been studied, with tractability of some and NP-hardness of others [4, 19, 29]. These qualitative approximation tasks are examples of Promise Constraint Satisfaction Problems (PCSPs) [2, 7 BBKO21]. The contrasting complexity of these relaxations motivates studying which relations are promise-useful [3]: which relations admit a nontrivial relaxation such that the associated PCSP is tractable? Once a relation is known to be promise-useful, one can study which of its nontrivial relaxations yield tractable PCSPs.

In their series of works, Bhangale, Khot, and Minzer [16, 17, 14, 15, 18], and Bhangale, Khot, Liu, and Minzer [11] identified Abelian embeddings as an important structural feature for the quantitative approximation of satisfiable CSPs. Informally, such an embedding captures additive structure within a constraint relation. Bhangale et al. use this structure in a hybrid approximation algorithm combining the solution of equations over Abelian groups with semidefinite programming [18].

Definition 1.1. Suppose R⊆ArR \subseteq A^r is an rr-ary relation with A=dom⁡(R)A = \operatorname{dom}(R) and GG is an Abelian group. We say that RR admits an Abelian embedding to GG if there exist functions f1,…,fr:A→Gf_1,\ldots,f_r:A\to G such that (i) at least one of f1,…,frf_1,\ldots,f_r is nonconstant, and (ii) for all (x1,…,xr)∈R(x_1,\ldots,x_r)\in R we have ∑ifi(xi)=0\sum_i f_i(x_i)=0. We say simply that RR admits an Abelian embedding if it admits one to some Abelian group.

In this paper, we develop an approach to qualitative approximation based on Abelian embeddings and establish a sharp complexity dichotomy for approximating detrivialised equations over prime-order groups, a family of PCSPs whose promise relations admit such embeddings. In particular, we show that suitable Abelian embeddings are a structural source of promise-usefulness.

This algorithmic role of Abelian embeddings is complemented by recent hardness results based on connectivity properties of the promise relation. Extending work of Braverman, Khot, Lifshitz, and Minzer [12], Banakh, Barsukov, and Nakajima [6] show that, assuming the Rich 2-to-1 conjecture [13], every (nontrivial) qualitative approximation of a symmetric reconfigurable relation is NP-hard. Here symmetry means closure under permutations of coordinates, while reconfigurability is defined as follows.

Definition 1.2. A relation RR is reconfigurable if the graph whose vertices are tuples of RR, and where edges are drawn between tuples which differ in exactly one coordinate, is connected.

For symmetric relations, Abelian embeddability imposes a separation between tuples that cannot be overcome by local changes, while reconfigurability requires local changes to connect all tuples. Indeed, the two regimes are disjoint: if adjacent tuples differ in coordinate ii, then any Abelian embedding must assign the same value under fif_i to the two entries in that coordinate. Connectivity and symmetry therefore force every fif_i to be constant, so a reconfigurable relation admits no Abelian embedding. In fact, each detrivialised equations relation defined below has an edgeless reconfiguration graph. Our hardness results therefore concern promise relations at the opposite structural extreme from the reconfigurable relations covered by the framework of Banakh, Barsukov, and Nakajima [6].

Concurrent work of Chan and Ng [20] also highlights the algorithmic role of Abelian embeddings, showing that an algorithm combining SDP and constraint singleton AIP subsumes the hybrid algorithm of Bhangale, Khot, and Minzer [18]. Our tractability results give a complementary perspective for qualitative approximation (PCSPs).

Contributions. Our first contribution is a general reduction that uses suitable Abelian embeddings and roundings to strengthen the promise relation of a PCSP. The reduction applies to both decision and search, yielding a new source of tractability for qualitative approximation.

Our second contribution is a sharp complexity dichotomy for approximating detrivialised equations over prime-order groups.

Definition 1.3. Let GG be a finitely generated Abelian group. We define the ternary equations relation Eqn⁡(G)={(x,y,z)∈G3∣x+y+z=0}\operatorname{Eqn}(G) = \{(x,y,z) \in G^3 \mid x+y+z=0\}. Its detrivialised equations relation is Eqn⁡∗(G)={(x,y,z)∈Eqn⁡(G)∣x,y,z are not all equal}\operatorname{Eqn}^{*}(G) = \{(x,y,z) \in\operatorname{Eqn}(G) \mid x,y,z\text{ are not all equal}\}.

If a ternary relation RR contains a constant tuple (a,a,a)(a,a,a), then every instance of CSP⁡(R)\operatorname{CSP}(R) is satisfied by assigning aa to every variable. Detrivialisation removes precisely these tuples: Eqn⁡∗(G)\operatorname{Eqn}^{*}(G) is the largest subrelation of Eqn⁡(G)\operatorname{Eqn}(G) containing no constant tuple. When GG has no 33-torsion, as for Zp\mathbb{Z}_p with p≠3p \ne3, this amounts to deleting only (0,0,0)(0,0,0). For nontrivial GG, the identity map witnesses an Abelian embedding of Eqn⁡∗(G)\operatorname{Eqn}^{*}(G) into GG.

Although systems of equations over Zp\mathbb{Z}_p can be solved in polynomial time, CSP⁡(Eqn⁡∗(Zp))\operatorname{CSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p)), i.e. finding a solution to a system of homogeneous linear equations mod pp where no particular equation is assigned a constant tuple, is NP-hard.2

We therefore study a qualitative relaxation of this problem: given a system promised to have a solution over GG that is nonconstant on every equation, find a cc-colouring of its variables that makes every equation nonmonochromatic. This retains the nonconstancy requirement while discarding the equations themselves, leaving a colouring problem on the underlying hypergraph of constraints. We write NAE⁡c\operatorname{NAE}_c for the ternary not-all-equal relation on cc colours. For fixed cc, this is the largest target relation containing no constant tuple, and hence gives the weakest relaxation excluding constant solutions.3 For detrivialised equations over prime-order groups, the resulting problem is defined as follows.

Definition 1.4. Let pp be a prime and c≥2c \ge2. An instance of PCSP⁡(Eqn⁡∗(Zp),NAE⁡c)\operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) is given by a system of linear equations of the form x+y+z≡0(modp)x+y+z \equiv0 \pmod p. The goal is to output Yes if there exists a solution to this system over Zp\mathbb{Z}_p which is nonconstant on every equation, and No if there is not even a solution over NAE⁡c\operatorname{NAE}_c, i.e., a colouring of the variables with cc colours which renders each equation nonconstant.

For p=2p=2 and c=2c=2, PCSP⁡(Eqn⁡∗(Zp),NAE⁡c)\operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) is (isomorphic via Boolean complementation to) the 1-in-3 vs. NAE-3-SAT problem, shown tractable by Brakensiek and Guruswami [7]. For p=3p=3, PCSP⁡(Eqn⁡∗(Zp),NAE⁡c)\operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) corresponds to the 3-rainbow vs. cc-normal hypergraph colouring problem, studied by McDiarmid [30], who gave a randomised algorithm. A deterministic algorithm for p∈{2,3}p \in\{2,3\} and all c≥2c \ge2 follows from the tractability of the problem for p=c=2p=c=2 via homomorphic relaxation [BBKO21, Definition 4.6].

For p≥5p \ge5 however, the story is more complicated, as the following theorem shows. Note that for p≥5p \ge5 the problem is well-defined for c≥3c \ge3; when c=2c=2, some instances satisfy both the Yes and No conditions.

Theorem 1.5. Fix a prime p≥5p \ge5. PCSP⁡(Eqn⁡∗(Zp),NAE⁡c)\operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_p),\operatorname{NAE}_c) is (i) solvable in polynomial time if c≥4c \ge4, (ii) NP-hard if c=3c=3.

In fact we prove a stronger theorem.

Theorem 1.6. Fix a nontrivial finite Abelian group GG without elements of order 2 or 3. Then PCSP⁡(Eqn⁡∗(G),NAE⁡c)\operatorname{PCSP}(\operatorname{Eqn}^{*}(G),\operatorname{NAE}_c) is (i) solvable in polynomial time if c≥4c \ge4, (ii) NP-hard if c=3c=3 (provided the problem is well-defined).

The algorithm that solves this problem is a singleton algorithm [35], and its correctness relies on the fact that Eqn⁡∗(G)\operatorname{Eqn}^{*}(G) has an Abelian embedding to GG. In fact, the algorithm generalises easily to one which works for all templates PCSP⁡(R,NAE⁡c)\operatorname{PCSP}(R,\operatorname{NAE}_{c}), where RR has an Abelian embedding to a group with a “cc-rounding”. We present this more general algorithm along with the notion of cc-rounding in § 3, and show that the tractability part of the theorem above is a simple consequence. However, neither kk-consistency (for any fixed kk) nor the combined Basic Linear Programming and Affine Integer Programming (BLP+AIP) relaxation [BGWZ20] solves this problem (Appendix § 7.§ 1). Thus this is an example of a natural fragment of finite-domain PCSPs solvable by a singleton algorithm but not by either of the above methods.

Algorithmic results. We illustrate the algorithm by running it on a small instance of PCSP⁡(Eqn⁡∗(Z5),NAE⁡4)\operatorname{PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_{5}),\operatorname{NAE}_{4}). In fact, we will run it on the search version of the problem, denoted by Search-PCSP⁡(Eqn⁡∗(Z5),NAE⁡4)\operatorname{Search\text{-}PCSP}(\operatorname{Eqn}^{*}(\mathbb{Z}_{5}),\operatorname{NAE}_{4}): Given an instance that is promised to admit a solution over Eqn⁡∗(Z5)\operatorname{Eqn}^{*}(\mathbb{Z}_{5}), the goal is to find a solution over NAE⁡4\operatorname{NAE}_{4}. Consider the instance with variable set {a,b,c,d,e,f,g,x,y,z,u}\{a,b,c,d,e,f,g,x,y,z,u\} and the following eight equation constraints, where all equations are modulo 5:

C1: a+b+e=0,C2: a+c+d=0,C3: a+d+g=0,C4: a+e+f=0,C5: b+c+g=0,C6: b+d+f=0,C7: x+y+z=0,C8: a+x+u=0.\begin{aligned} C_{1}:&\ a+b+e=0, & C_{2}:&\ a+c+d=0, & C_{3}:&\ a+d+g=0, & C_{4}:&\ a+e+f=0,\\ C_{5}:&\ b+c+g=0, & C_{6}:&\ b+d+f=0, & C_{7}:&\ x+y+z=0, & C_{8}:&\ a+x+u=0. \end{aligned}

This is a valid instance: the assignment

a=0,b=1,c=2,d=3,e=4,f=1,g=2,x=1,y=1,z=3,u=4a=0,\quad b=1,\quad c=2,\quad d=3,\quad e=4,\quad f=1,\quad g=2,\quad x=1,\quad y=1,\quad z=3,\quad u=4

satisfies every equation nontrivially. The algorithm is not given the displayed assignment; it only uses the promise that such an assignment exists. We will now explain how the algorithm works (illustrated in Figure 1).

An example run of the algorithm

Figure 1. An example run of the algorithm.

We start by picking some constraint, say C1C_{1}. We know there exists some solution to the system such that C1C_{1} does not get assigned the tuple (0,0,0)(0,0,0). We find such a solution as follows. We choose a variable in C1C_{1}, say aa, and look (using Gaussian elimination) for a solution to the system with aa fixed to 1 or some other nonzero value. In this case, no such solution exists, so we move on to another variable in C1C_{1}, say bb, and look for a solution to the system with bb fixed to 1. We find such a solution s1s_{1}, and fix the values of all variables that got a nonzero value. Next, we repeat the same process for the subinstance induced on the remaining variables. The final NAE⁡4\operatorname{NAE}_{4}-solution γ\gamma assigns each variable the first nonzero value it receives in s1,s2,s3s_{1},s_{2},s_{3}. The end row of the lower table in Figure 1 lists the final tuple assigned to each constraint and shows that every constraint is nonmonochromatic. Informally, the reason this works is that, in the first step at which any variable in a constraint is coloured at all, it must be the case that 2 or 3 variables in that constraint are coloured, and indeed coloured with at least 2 different values. Hence, no matter what colour is assigned to the remaining variable (if it exists), the constraint is satisfied.

The algorithm as a reduction. Viewed more generally, the algorithm yields a polynomial-time reduction between the original PCSP and a PCSP obtained by restricting (and thus strengthening) its promise relation. The previous example is the special case in which the restricted promise relation is empty, and thus the target of the reduction is a trivial problem. The existence of this reduction contributes to the goal of the algebraic approach to PCSPs, which seeks to understand the complexity of all PCSPs through the algebraic characterisation of reductions between them [BBKQ21, BK22, DO24, BHZ27]. To this end, we show (Appendix § 7.§ 2) that the reduction can be implemented using (Constraint) Singleton AIP (CSingl AIP). We then characterise CSingl AIP reductions algebraically, along the lines of Dalmau and Opršal [24] (Appendix § 7.§ 3).

Additive combinatorics. Our (hardness) results use tools and ideas from additive combinatorics. Fix some prime p≥5p \ge5. We call a partition of Zp\mathbb{Z}_{p} into three sets A1,A2,A3A_{1},A_{2},A_{3} valid if the only solution to x+y+z≡0(modp)x+y+z\equiv0\pmod{p} with x,y,zx,y,z all in the same part is (0,0,0)(0,0,0). Validity is preserved by permuting the parts and by multiplying every element by the same nonzero scalar. A first step in the hardness proof is to classify these partitions: for every prime p≥7p \ge7, there is exactly one up to these symmetries.

Theorem 1.7. For every prime p≥7p \ge7, up to multiplication by a constant and permutation of parts, there exists exactly one valid partition of Zp\mathbb{Z}_p, namely the partition that puts xx into A1+⌊3x/p⌋A_{1+\lfloor3x/p\rfloor}.

This fact follows from an application of the Cauchy–Davenport theorem, together with Vosper’s theorem. It does not hold for p=5p=5, as shown by the theorem below, which can be proved by a simple case analysis. The full proofs of both theorems are in Appendix § 8.

Theorem 1.8. Up to multiplication by a constant and permutation of parts, there exist exactly two valid partitions of Z5\mathbb{Z}_5, namely {{2,3},{4},{0,1}}\{\{2,3\},\{4\},\{0,1\}\} and {{2,3},{1,4},{0}}\{\{2,3\},\{1,4\},\{0\}\}.

Preliminaries

We will only deal with PCSPs with a single relation. Therefore, we will specialise all of our notation and definitions for this case. Furthermore, we will leave the domains of relations implicit, for simplicity.4

References

  1. [2]Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-Sat is NP-hard. SIAM J. Comput., 46(5):1554–1573, 2017. doi:10.1137/15M1006507.DOI
  2. [3]Per Austrin, Johan Håstad, and Björn Martinsson. On the Usefulness of Promises, pages 6332–6378. 2026. doi:10.1137/1.9781611978971.228.DOI
  3. [4]Libor Barto, Diego Battistelli, and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case. In Proc. 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), volume 187 of LIPIcs, pages 10:1–10:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2021.10.DOI
  4. [6]Demian Banakh, Alexey Barsukov, and Tamio-Vesa Nakajima. Towards Infinite PCSP: A Dichotomy for Monochromatic Cliques. In Claudia Faggian and Joost-Pieter Katoen, editors, Proc. 41st Annual Symposium on Logic in Computer Science (LICS’26), volume 380 of LIPIcs, pages 13:1–13:28, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.LICS.2026.13.DOI
  5. [7]Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy. SIAM J. Comput., 50(6):1663–1700, 2021. arXiv:1704.01937, doi:10.1137/19M128212X.
  6. [9]Libor Barto, Maximilian Hadek, and Dmitriy Zhuk. Toward a uniform algorithm and uniform reduction for constraint problems. In Proc. 2027 ACM-SIAM Symposium on Discrete Algorithms (SODA’27), 2027. arXiv:2604.06335.arxiv.org/abs/2604.06335
  7. [11]Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer. On inverse theorems and combinatorial lines. In Proc. 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS’25), pages 1672–1684. IEEE, 2025. doi:10.1109/FOCS63196.2025.00089.DOI
  8. [12]Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer. An invariance principle for the multi-slice, with applications. Advances in Mathematics, 480:110460, November 2025. doi:10.1016/j.aim.2025.110460.DOI
  9. [13]Mark Braverman, Subhash Khot, and Dor Minzer. On rich 2-to-1 games. In Proc. 12th Innovations in Theoretical Computer Science Conference (ITCS’21), volume 185 of LIPIcs, pages 27:1–27:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.27.DOI
  10. [14]Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: III. In Proc. 55th Annual ACM Symposium on Theory of Computing (STOC’23), pages 643–655. ACM, 2023. doi:10.1145/3564246.3585121.DOI
  11. [15]Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: IV. In Proc. 56th Annual ACM Symposium on Theory of Computing (STOC’24), pages 1423–1434. ACM, 2024. doi:10.1145/3618260.3649610.DOI
  12. [16]Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-CSPs: I. Comput. Complex., 34(2):8, 2025. doi:10.1007/S00037-025-00267-6.DOI
  13. [17]Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-CSPs: II. Comb. Probab. Comput., 34(6):857–926, 2025. doi:10.1017/S0963548325100114.DOI
  14. [18]Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-CSPs: V. TheoreticS, 5:9, 2026. doi:10.46298/THEORETICS.26.9.DOI
  15. [19]Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima, and Stanislav Živný. 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. ACM Transactions on Computational Logic, 26(2):1–22, April 2025. doi:10.1145/3719007.DOI
  16. [20]Siu On Chan and Hiu Tsun Ng. Universal Abelian Embedding and Affine Relaxation for CSP, 2026. Technical report. URL: https://eccc.weizmann.ac.il/report/2026/273/.
  17. [21]Lorenzo Ciardo and Stanislav Živný. CLAP: A new algorithm for promise CSPs. SIAM J. Comput., 52(1):1–37, 2023. arXiv:2107.05018, doi:10.1137/22M1476435.DOI
  18. [22]H. Davenport. On the addition of residue classes. Journal of the London Mathematical Society, s1-10(1):30–32, 1935. doi:10.1112/jlms/s1-10.37.30.DOI
  19. [24]Victor Dalmau and Jakub Opršal. Local consistency as a reduction between constraint satisfaction problems. In Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 1–15, July 2024. arXiv:2301.05084 [cs.LO]. doi:10.1145/3661814.3662068.DOI
  20. [27]Michel X. Goemans and David P. Williamson. Approximation algorithms for Max-3-Cut and other problems via complex semidefinite programming. Journal of Computer and System Sciences, 68(2):442–470, 2004. doi:10.1016/j.jcss.2003.07.012.DOI
  21. [28]Pavol Hell and Jaroslav Nešetril. Graphs and Homomorphisms. July 2004. doi:10.1093/acprof:oso/9780198528173.001.0001.DOI
  22. [29]Andrei Krokhin and Danny Vagnozzi. Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard. In Proc. 53rd International Colloquium on Automata, Languages, and Programming (ICALP’26), volume 374 of LIPIcs, pages 184:1–184:18, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2026.184.DOI
  23. [30]Colin McDiarmid. A Random Recolouring Method for Graphs and Hypergraphs. Combinatorics, Probability and Computing, 2(3):363–365, 1993. doi:10.1017/S0963548300000730.DOI
  24. [31]Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1986.
  25. [32]T. Szőnyi. COMBINATORIAL PROBLEMS FOR ABELIAN GROUPS ARISING FROM GEOMETRY. Periodica Polytechnica Transportation Engineering, 19(1-2):91–100, 1991.
  26. [33]José Felipe Voloch. On the Completeness of Certain Plane Arcs-II. European Journal of Combinatorics, 11(5):491–496, September 1990. doi:10.1016/S0195-6698(13)80032-7.DOI
  27. [34]A. G. Vosper. The critical pairs of subsets of a group of prime order. Journal of the London Mathematical Society, s1-31(2):200–205, 1956. doi:10.1112/jlms/s1-31.2.200.DOI
  28. [35][Zhu26] Dmitriy Zhuk. Singleton algorithms for the Constraint Satisfaction Problem. In Proc. 67th IEEE Annual Symposium on Foundations of Computer Science (FOCS’26), 2026. arXiv:2509.18434.arxiv.org/abs/2509.18434

Paper details

vlnc:W_fp97f9wp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 4.8 (bare), Claude Opus 5 (bare), Claude Sonnet 5 (bare), DeepSeek, GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents