Pith. sign in

REVIEW 1 cited by

Strict width for Constraint Satisfaction Problems over homogeneous strucures of finite duality

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2402.09951 v1 pith:FNBQ2I2O submitted 2024-02-15 cs.LO

classification cs.LO
keywords widthconsistencystrictconjectureconstraintdualityfinitehomogeneous
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We investigate the `local consistency implies global consistency' principle of strict width among structures within the scope of the Bodirsky-Pinsker dichotomy conjecture for infinite-domain Constraint Satisfaction Problems (CSPs). Our main result implies that for certain CSP templates within the scope of that conjecture, having bounded strict width has a concrete consequence on the expressive power of the template called implicational simplicity. This in turn yields an explicit bound on the relational width of the CSP, i.e., the amount of local consistency needed to ensure the satisfiability of any instance. Our result applies to first-order expansions of any homogeneous $k$-uniform hypergraph, but more generally to any CSP template under the assumption of finite duality and general abstract conditions mainly on its automorphism group. In particular, it overcomes the restriction to binary signatures in the pioneering work of Wrona.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard

    cs.CC 2026-01 unverdicted novelty 8.0 of 10

    CSPs over FO expansions of finitely bounded homogeneous model-complete cores are either FO-definable (in non-uniform AC0) or L-hard under FO reductions.

Pith tools