Pith. sign in

REVIEW 4 major objections 4 minor 38 references

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries

T0 review · 4 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that every constraint satisfaction problem of unbounded width requires Ω(n) queries to test satisfiability in the bounded-degree model, making such problems maximally hard to test and unifying all previously known linear lo

desk verdict The main theorem is very likely right and genuinely unifies the known linear lower bounds for CSP testing; the proof is careful, and the only real risk is the cited universal-algebraic black box. read the letter →

arxiv 2510.27012 v3 pith:4NTP4XIP submitted 2025-10-30 cs.CC cs.DS

Yumou Fei This is my paper · ORCID
classification cs.CCcs.DS MSC 68Q1768W20
keywords propertytestingbounded-degreemodelconstraintsatisfactionproblemsunboundedwidthquerylowerboundsMaxCSPlinearequationsoverabeliangroupsuniversalalgebra
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that every constraint satisfaction problem (CSP) whose template has unbounded width is maximally hard to test in the bounded-degree query model: any tester that distinguishes satisfiable instances from instances far from satisfiable must read a linear number of variables. The result matters because it turns a scattered collection of linear lower bounds for specific problems like graph 3-coloring, 3SAT, and systems of linear equations into one theorem covering the entire unbounded-width class. The proof works by reducing the testing task for any unbounded-width CSP to testing equations of the form x+y+z=b over a finite abelian group, using universal-algebraic facts to justify the reduction and a random-regular-hypergraph gadget to enforce constant values. If correct, it says the only CSPs with any hope of sublinear testers are the bounded-width ones.

What carries the argument

The hardness seed is the family of ternary sum relations 3SumG, defined by x+y+z=b over a finite abelian group G. The load-bearing bridge is the universal-algebraic lemma that every repetition-closed unbounded-width template, after adding constant relations, can generate lifted copies of these 3SumG relations on a subset D′ of its domain. The endomorphism relation EndΓ on the template provides a sub-unique relation, allowing a random regular hypergraph gadget to force variables to nearly constant values and thereby remove the added constants. Everything is measured in the bounded-degree query model, where the tester sees constraints incident to queried variables and distance is the number of

What would settle it

Exhibit a repetition-closed core of unbounded width whose polymorphism algebra generates a variety admitting neither the unary nor the affine type; then the universal-algebraic simulation lemma fails. Alternatively, produce any ε-tester for a single unbounded-width CSP that makes o(n) queries, which would directly contradict Theorem 1.6.

Watch

Extended reading notes

Core claim

The central claim is that width, a structural parameter measuring whether satisfiability can be certified by local consistency checks, draws the hardness line for testing satisfiability in the bounded-degree model: unbounded width forces Ω(n) queries. The proof's bridge is a lemma stating that any repetition-closed unbounded-width template, once constant relations are added, can generate ternary relations that behave exactly like x+y+z=b over a finite abelian group on a subset D′ of its domain. Since testing equations of that form is known to require linear queries, the paper builds a query-preserving reduction from those equations to the target CSP; a gadget built from an expander-like rand

Load-bearing premise

The whole reduction depends on the lemma that any repetition-closed unbounded-width template, after adding constant relations, can generate ternary relations equivalent to x+y+z=b over some finite abelian group; the appendix only sketches the supporting universal-algebraic theorem, so if that bridge fails, the argument collapses.

Editorial extensions

If this is right

  • Every unbounded-width CSP template has an unconditional linear-query lower bound for testing satisfiability in the bounded-degree model, with no reliance on P vs NP.
  • All previously known linear lower bounds — for k-coloring of ℓ-uniform hypergraphs with (k,ℓ)≠(2,2), for 3SAT, and for systems of linear equations — become special cases of one theorem.
  • The same lower bound applies to the perfect-completeness MaxCSP problem, i.e., distinguishing value 1 from value at most 1−ε, on instances with Θ(n) constraints.
  • Bounded-width CSPs are left as the only remaining candidates for sublinear-query testers; the paper poses as an open problem whether all bounded-width templates actually admit such testers.
  • Because the lower bound is proved against sublinear-query algorithms, it does not follow from NP-hardness and is a strictly unconditional form of hardness in this model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: if the reduction here composes with the known phenomenological connection between bounded-degree query algorithms and multi-pass streaming (a connection the paper itself raises as a question), the linear-query lower bound may port to a linear-space lower bound for approximating MaxCSP on unbounded-width templates in streaming.
  • Editorial inference: the theorem suggests that query complexity of satisfiability testing is governed by bounded width alone, so the next quantitative question is the exact exponent for bounded-width templates — for example, whether 2COL's Θ(√n) behavior generalizes to all bounded-width cases or splits further.
  • Editorial inference: a concrete testable extension is whether the reduction can be made to show that the optimal soundness gap ε for a given template is computable from its polymorphism algebra; the paper leaves the analogous question for 3COL open.
  • Editorial inference: the proof's reliance on the universal-algebraic simulation lemma suggests that any attempt to build a sublinear tester for a bounded-width CSP should look for structure that provably excludes the affine or unary type in its polymorphism variety.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proves that for every finite CSP template (D,Γ) of unbounded width, there are constants ε,d such that any ε-tester for satisfiability of CSP(Γ) in the bounded-degree model BD(d,n) must make Ω(n) queries. The proof combines the BOT02 linear-query lower bound for 3SUM-type linear equations with universal-algebraic results: it first shows (Lemma 3.4) that an unbounded-width repetition-closed template, after adding constant relations, can simulate ternary relations of the form φ(x1)+φ(x2)+φ(x3)=b over a finite abelian group; it then eliminates the constants by an expander gadget built from the Endomorphism relation of a core, and carries out the standard completeness/soundness/indistinguishability analysis. The claimed unification covers all previously known linear lower bounds for 3COL, 3SAT, 3LIN, and hypergraph colorability, and more generally all unbounded-width CSPs.

Significance. If the proof is correct, this is a strong and natural unification: it replaces case-by-case linear lower bounds with one theorem over the whole unbounded-width class, and it connects the property-testing question to the robust-satisfiability dichotomy of Dalmau–Krokhin and Barto–Kozik. The paper is well structured, gives careful statements of completeness and soundness, and includes appendices for the random-hypergraph lemmas and the Galois duality step. The main weakness is that the load-bearing bridge from unbounded width to linear equations (Theorem 3.2/Appendix E) is a sketch relying on a combination of deep universal-algebraic results, and several supporting lemmas in the appendices are stated or proved in a way that needs correction.

major comments (4)
  1. [§3 / Appendix E, Theorem 3.2 and Lemma 3.4] The reduction's central step is the claim that an unbounded-width core with idempotent polymorphism algebra has a homomorphic image of a subalgebra that is a strictly simple idempotent algebra of unary or affine type whose operations belong to Pol(3SumG). Appendix E derives this by citing [BK14], [Val09], and [Sze92] in sequence, but Corollary E.4 is asserted without a proof of the unary-type classification. The unary-type case is not obvious: it requires proving that the strictly simple unary-type algebra is term-equivalent to a projection algebra on a 2-element set (or otherwise affine over Z2) so that its operations preserve 3SumG. Since Lemma 3.4 is the bridge from unbounded width to the linear-equation hardness, this step needs either a precise quotation of the relevant classification theorem or a self-contained proof.
  2. [Appendix D, Proposition D.2] As stated, item (2) is false. For d≥2, every vertex of [n]×[3] is incident to d hyperedges, one in each perfect matching M(i); therefore no total order of the full union ∪_i M(i) can have the property that every hyperedge has a vertex not appearing in any earlier hyperedge. The proof appears to intend the union of the hyperedges that are entirely contained in the chosen subset U (i.e., ∪_i M(i)[U]). The proposition must be restated and proved for that object. This proposition is used in the proof sketch of Lemma 4.7, so the indistinguishability of the base distributions is affected.
  3. [Appendix D, proof of Lemma 5.4, Case 1] The inequality 1-(1-2ε)^D ≤ 1-2ε is incorrect for D>1. For example, with ε=0.01 and D=10, the left side is about 0.183, while the right side is 0.02. The expectation E_v[R((τ(v_x))_x)] is at most 1-(1-2ε)^D ≈ 2Dε, not 1-2ε. The subsequent martingale concentration argument can still be made to work by absorbing the factor D into the choice of ℓ, but as written the proof does not establish the claimed probability bound.
  4. [§5.3, Lemma 5.7] The query-simulation argument is not fully rigorous. A query to a variable in Vconst or Vaux(1) can reveal a constraint belonging to the copy I_b of a particular original constraint C with right-hand side b; the identity of that copy depends on b, and the oracle on the original instance I may return a different constraint incident to the same original variable. The statement that such a query 'reveals no more information than a query to (j,1) in I' therefore needs a precise coupling or a query-by-query simulation. A constant-factor increase in the number of queries would be acceptable, but the lemma as stated assumes a one-to-one replacement and is not justified by the bullets given.
minor comments (4)
  1. [References / §3] Theorem 3.2 is attributed to [BK14], but Appendix E shows it is a combination of [BK14], [Val09], and [Sze92]. The citation should be adjusted so that the reader knows the statement is not literally one theorem of [BK14].
  2. [§5.4, Lemma 5.6, Appendix D] There are several typos: 'reptition-closed' in §5.4, 'instace' in Lemma 5.6, 'assignemnt' in Appendix D, and 'support' is used before being defined. These are cosmetic but should be fixed.
  3. [§2.1 / Definition 2.3] The notation {R} for the repetition closure of a single relation is easy to confuse with the singleton set; a different symbol or a clarifying sentence would improve readability.
  4. [Appendix E] The appendix would benefit from stating the exact theorem of Szendrei used for the unary-type and affine-type cases, rather than only citing Theorem 6.1 in prose; this is related to the first major comment and would reduce the burden on the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; the derivation chain rests on external published results and self-contained reductions.

full rationale

Walking the derivation chain: Theorem 1.6/1.8 reduces unbounded-width CSP testing to hardness for 3SumG via Lemma 3.4, which is translated from Theorem 3.2. Theorem 3.2 is cited to [BK14] with ingredients from [Val09] and [Sze92]; these are external research groups, not the author's own prior work. The base hardness of 3SumG is Theorem 4.1, attributed to [BOT02], an external published lower bound. The reduction map T[I] is constructed explicitly (Section 5.2) and its completeness, soundness, and indistinguishability are proved in Lemmas 5.5, 5.6, and 5.7. Lemma 3.4 itself is proved in the paper from Theorem 3.2, Proposition A.4, and Galois duality (Theorem 2.16, proved in Appendix C); the relations R in (3.1) are shown to be preserved by all polymorphisms and hence generated, not assumed. The only self-citations are [FMW25a, FMW25b] in the discussion section (Sections 1.2.4 and 1.3), where they are used as contextual motivation for an open question, not as load-bearing premises for the main theorem. The reviewer-skeptic concern about the universal-algebra bridge (Theorem 3.2 / Appendix E being only sketched and reliant on a classification theorem) is a correctness-risk or rigor concern, not a circularity concern: the paper does not define unbounded width in terms of affine-type varieties, does not fit any parameter from the target result, and does not invoke an unverified self-citation to force its conclusion. No step reduces, by construction or definition, to the theorem being proved.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

All constants in the proof (ε,d,α,r1,r2,ℓ,γ) are chosen to satisfy explicit inequalities and are not fitted to data. The paper's contribution is a reduction, and everything else is imported from published theorems; the most important imports are listed as axioms. No invented entities or free parameters beyond the template-level constants appear.

assumptions (6)
  • standard math Barto–Kozik characterization: a core relational structure has unbounded width iff its idempotent polymorphism algebra generates a variety admitting the unary or affine type.
    Invoked in Appendix E to derive Theorem 3.2; this is the bridge from unbounded width to affine/unary algebras.
  • standard math Valeriote's theorem and Szendrei's classification: if a finite idempotent algebra admits unary/affine type then a homomorphic image of a subalgebra is strictly simple, and strictly simple idempotent unary/affine algebras have all operations preserving 3SumG for some abelian group G.
    Together with Barto–Kozik this yields Lemma 3.4's simulation of linear equations.
  • domain assumption BOT02 hardness for random 3SumG instances extends from G=Z/2Z to every finite abelian group.
    Footnote 12 says the proof 'can easily be adapted'; no proof is given, and the reduction from unbounded-width CSPs relies on it.
  • domain assumption Random ℓ-regular k-partite hypergraphs satisfy the local-sparsity and concentration lemmas (Lemmas 4.7 and 5.4).
    Proved only in sketches in Appendix D; Lemma 5.4 is new and used to simulate constant relations via expander gadgets.
  • standard math Geiger's Galois duality: a relation is generated by Γ iff it is preserved by Pol(Γ), for irredundant relations on repetition-closed templates.
    Used in Lemma 3.4 to turn polymorphism preservation into gadget simulation.
  • standard math Homomorphically equivalent templates have equal instance values and share bounded width.
    Reduces general unbounded-width templates to cores in Section 5.4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Unbounded-width CSPs are Untestable in a Sublinear Number of Queries." pith.science (2026). https://pith.science/paper/4NTP4XIP

@misc{pith2026251027012,
  author       = {Pith},
  title        = {Pith review of: Unbounded-width CSPs are Untestable in a Sublinear Number of Queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4NTP4XIP}},
  note         = {Machine review of arXiv:2510.27012}
}
abstract

The bounded-degree query model, introduced by Goldreich and Ron (\textit{Algorithmica, 2002}), is a standard framework in graph property testing and sublinear-time algorithms. Many properties studied in this model, such as bipartiteness and 3-colorability of graphs, can be expressed as satisfiability of constraint satisfaction problems (CSPs). We prove that for the entire class of \emph{unbounded-width} CSPs, testing satisfiability requires $\Omega(n)$ queries in the bounded-degree model. This result unifies and generalizes several previous lower bounds. In particular, it applies to all CSPs that are known to be $\mathbf{NP}$-hard to solve, including $k$-colorability of $\ell$-uniform hypergraphs for any $k,\ell \ge 2$ with $(k,\ell) \neq (2,2)$. Our proof combines the techniques from Bogdanov, Obata, and Trevisan (\textit{FOCS, 2002}), who established the first $\Omega(n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

38 extracted references · 3 linked inside Pith

  1. [3]

    Testing satisfiability

    Noga Alon and Asaf Shapira. Testing satisfiability. Journal of Algorithms , 47(2):87--103, 2003

    2003

  2. [1]

    Property testing in bounded degree hypergraphs

    Hugo Aaronson, Gaia Carenini, and Atreyi Chanda. Property testing in bounded degree hypergraphs. arXiv preprint arXiv:2502.18382 , 2025

    arXiv 2025

  3. [2]

    Polynomial time approximation schemes for dense instances of np-hard problems

    Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing , pages 284--293, 1995

    1995

  4. [4]

    The collapse of the bounded width hierarchy

    Libor Barto. The collapse of the bounded width hierarchy. Journal of Logic and Computation , 26(3):923--943, 2014

    2014

  5. [5]

    Constraint satisfaction problems solvable by local consistency methods

    Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM (JACM) , 61(1):1--19, 2014

    2014

  6. [6]

    Robustly solvable constraint satisfaction problems

    Libor Barto and Marcin Kozik. Robustly solvable constraint satisfaction problems. SIAM Journal on Computing , 45(4):1646--1669, 2016

    2016

  7. [7]

    A lower bound for testing 3-colorability in bounded-degree graphs

    Andrej Bogdanov, Kenji Obata, and Luca Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages 93--102. IEEE, 2002

    2002

  8. [8]

    Notes on csps and polymorphisms

    Zarathustra Brady. Notes on csps and polymorphisms. arXiv preprint arXiv:2210.07383 , 2022

    arXiv 2022

Show all 38 references
  1. [9]

    Every minor-closed property of sparse graphs is testable

    Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. Advances in Mathematics , 223:2200--2218, 2010

    2010

  2. [10]

    Linear space streaming lower bounds for approximating csps

    Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. Linear space streaming lower bounds for approximating csps. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 275--288, 2022

    2022

  3. [11]

    Sketching approximability of all finite csps

    Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Sketching approximability of all finite csps. Journal of the ACM , 71(2):1--74, 2024

    2024

  4. [12]

    Planar graphs: Random walks and bipartiteness testing

    Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Structures & Algorithms , 55(1):104--124, 2019

    2019

  5. [13]

    Robust satisfiability for csps: Hardness and algorithmic results

    V \' ctor Dalmau and Andrei Krokhin. Robust satisfiability for csps: Hardness and algorithmic results. ACM Transactions on Computation Theory (TOCT) , 5(4):1--25, 2013

    2013

  6. [14]

    A dichotomy theorem for multi-pass streaming csps

    Yumou Fei, Dor Minzer, and Shuo Wang. A dichotomy theorem for multi-pass streaming csps. arXiv preprint arXiv:2509.11399 , 2025

    2025

  7. [15]

    Multi-pass streaming lower bounds for approximating max-cut

    Yumou Fei, Dor Minzer, and Shuo Wang. Multi-pass streaming lower bounds for approximating max-cut. arXiv preprint arXiv:2503.23404 , 2025

    2025 arXiv

  8. [16]

    The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory

    Tom \'a s Feder and Moshe Y Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing , 28(1):57--104, 1998

    1998

  9. [17]

    Closed systems of functions and predicates

    David Geiger. Closed systems of functions and predicates. Pacific journal of mathematics , 27(1):95--100, 1968

    1968

  10. [18]

    Property testing and its connection to learning and approximation

    Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM) , 45(4):653--750, 1998

    1998

  11. [19]

    A sublinear bipartiteness tester for bounded degree graphs

    Oded Goldreich and Dana Ron. A sublinear bipartiteness tester for bounded degree graphs. Combinatorica , 19(3):335--373, 1999

    1999

  12. [20]

    Property testing in bounded degree graphs

    Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica , 32(2):302--343, 2002

    2002

  13. [21]

    On testing expansion in bounded-degree graphs

    Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. In Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation , pages 68--75. Springer, 2011

    2011

  14. [22]

    Tight bounds on the approximability of almost-satisfiable horn sat and exact hitting set

    Venkatesan Guruswami and Yuan Zhou. Tight bounds on the approximability of almost-satisfiable horn sat and exact hitting set. Theory of Computing , 8(1):239--267, 2012

    2012

  15. [23]

    Some optimal inapproximability results

    Johan H stad. Some optimal inapproximability results. Journal of the ACM (JACM) , 48(4):798--859, 2001

    2001

  16. [24]

    The structure of finite algebras , volume 76

    David Hobby and Ralph McKenzie. The structure of finite algebras , volume 76. American Mathematical Society, 1988

    1988

  17. [25]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing , pages 767--775, 2002

    2002

  18. [26]

    An optimal space lower bound for approximating max-cut

    Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating max-cut. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 277--288, 2019

    2019

  19. [27]

    Streaming lower bounds for approximating max-cut

    Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating max-cut. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1263--1282. SIAM, 2014

    2014

  20. [28]

    Bounded width problems and algebras

    Benoit Larose and L \'a szl \'o Z \'a dori. Bounded width problems and algebras. Algebra universalis , 56(3):439--466, 2007

    2007

  21. [29]

    Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every csp? In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 245--254, 2008

    2008

  22. [30]

    Streaming algorithms via local algorithms for maximum directed cut

    Raghuvansh R Saxena, Noah G Singer, Madhu Sudan, and Santhoshini Velusamy. Streaming algorithms via local algorithms for maximum directed cut. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3392--3408. SIAM, 2025

    2025

  23. [31]

    A survey on strictly simple algebras and minimal varieties

    \'A gnes Szendrei. A survey on strictly simple algebras and minimal varieties. In Research and Exposition in Mathematics , pages 209--239. Heldermann Verlag, Berlin, 1992

    1992

  24. [32]

    Non-approximability results for optimization problems on bounded degree instances

    Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the thirty-third annual ACM symposium on Theory of computing , pages 453--461, 2001

    2001

  25. [33]

    A subalgebra intersection property for congruence distributive varieties

    Matthew A Valeriote. A subalgebra intersection property for congruence distributive varieties. Canadian Journal of Mathematics , 61(2):451--464, 2009

    2009

  26. [34]

    Probability in high dimension (lecture notes), 2014

    Ramon van Handel. Probability in high dimension (lecture notes), 2014

    2014

  27. [35]

    Models of random regular graphs

    Nicholas Charles Wormald. Models of random regular graphs. In Surveys in Combinatorics, 1999 , pages 239--298. 1999

    1999

  28. [36]

    Query-number preserving reductions and linear lower bounds for testing

    Yuichi Yoshida and Hiro Ito. Query-number preserving reductions and linear lower bounds for testing. IEICE transactions on information and systems , 93(2):233--240, 2010

    2010

  29. [37]

    Property testing on k-vertex-connectivity of graphs

    Yuichi Yoshida and Hiro Ito. Property testing on k-vertex-connectivity of graphs. Algorithmica , 62(3):701--712, 2012

    2012

  30. [38]

    Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree csp

    Yuichi Yoshida. Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree csp. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 665--674, 2011

    2011

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.