On the public citation graph

The collapse of the bounded width hierarchy

0 signed · 71 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-3-540-92800-3openalex-snapshot
Complexity of Constraints
inferredcites →https://doi.org/10.1007/978-3-540-92800-3_4openalex-snapshot
Recent Results on the Algebraic Approach to the CSP
inferredcites →https://doi.org/10.1007/978-3-540-92800-3_5openalex-snapshot
Dualities for Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1007/978-3-540-92800-3_8openalex-snapshot
Constraint Satisfaction Problems with Infinite Templates
inferredcites →https://doi.org/10.1007/s00012-007-2012-6openalex-snapshot
Bounded width problems and algebras
inferredcites →https://doi.org/10.1007/s00012-008-2122-9openalex-snapshot
Existence theorems for weakly symmetric operations
inferredcites →https://doi.org/10.1007/s00012-015-0327-2openalex-snapshot
Characterizations of several Maltsev conditions
inferredcites →https://doi.org/10.1007/s00012-015-0338-zopenalex-snapshot
Mal’tsev conditions, lack of absorption, and solvability
inferredcites →https://doi.org/10.1016/0012-365x(92)90282-kopenalex-snapshot
The core of a graph
inferredcites →https://doi.org/10.1016/j.ipl.2008.10.005openalex-snapshot
There are no pure relational width 2 constraint satisfaction problems
inferredcites →https://doi.org/10.1016/j.jalgebra.2004.07.044openalex-snapshot
Combinatorial problems raised from 2-semilattices
inferredcites →https://doi.org/10.1093/logcom/exr039openalex-snapshot
Arc consistency and friends
inferredcites →https://doi.org/10.1109/focs.2009.32openalex-snapshot
Constraint Satisfaction Problems of Bounded Width
inferredcites →https://doi.org/10.1109/lics.2007.50openalex-snapshot
Tractability and learnability arising from algebras with few subpowers
inferredcites →https://doi.org/10.1137/s0097539700376676openalex-snapshot
Classifying the Complexity of Constraints Using Finite Algebras
inferredcites →https://doi.org/10.1137/s0097539794266766openalex-snapshot
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
inferredcites →https://doi.org/10.1142/s021819670900524xopenalex-snapshot
OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
inferredcites →https://doi.org/10.1145/2213977.2214030openalex-snapshot
Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
inferredcites →https://doi.org/10.1145/2213977.2214061openalex-snapshot
Robust satisfiability of constraint satisfaction problems
inferredcites →https://doi.org/10.1145/2529989openalex-snapshot
Linear-Time Approximation for Maximum Weight Matching
inferredcites →https://doi.org/10.1145/2556646openalex-snapshot
Constraint Satisfaction Problems Solvable by Local Consistency Methods
inferredcites →https://doi.org/10.1145/2677161.2677165openalex-snapshot
Constraint satisfaction problem and universal algebra
inferredcites →https://doi.org/10.2168/lmcs-8(1:18)2012openalex-snapshot
A Bi-Directional Refinement Algorithm for the Calculus of (Co)Inductive Constructions
inferredcites →https://doi.org/10.2168/lmcs-8(1:7)2012openalex-snapshot
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
inferredcites →https://doi.org/10.4153/cjm-2009-023-2openalex-snapshot
A Subalgebra Intersection Property for Congruence Distributive Varieties

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-319-44953-1_9openalex-snapshot
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
inferred← citeshttps://doi.org/10.1007/978-3-319-77313-1_1openalex-snapshot
Constraint Satisfaction Problems: Complexity and Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_86openalex-snapshot
Sherali-Adams Relaxations for Valued CSPs
inferred← citeshttps://doi.org/10.1007/s00012-015-0327-2openalex-snapshot
Characterizations of several Maltsev conditions
inferred← citeshttps://doi.org/10.1007/s00012-016-0406-zopenalex-snapshot
Optimal strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties
inferred← citeshttps://doi.org/10.1007/s00012-018-0533-9openalex-snapshot
A characterization of idempotent strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties
inferred← citeshttps://doi.org/10.1007/s00012-026-00948-5openalex-snapshot
Smb algebras II: On the constraint satisfaction problem over semilattice of Mal’cev blocks
inferred← citeshttps://doi.org/10.1007/s10601-015-9198-6openalex-snapshot
Tractability in constraint satisfaction problems: a survey
inferred← citeshttps://doi.org/10.1016/j.ipl.2016.09.009openalex-snapshot
Equivariant algorithms for constraint satisfaction problems over coset templates
inferred← citeshttps://doi.org/10.1017/bsl.2015.25openalex-snapshot
THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
inferred← citeshttps://doi.org/10.1093/comjnl/bxx122openalex-snapshot
Exploring Directional Path-Consistency for Solving Constraint Networks
inferred← citeshttps://doi.org/10.1109/focs.2015.80openalex-snapshot
The Complexity of General-Valued CSPs
inferred← citeshttps://doi.org/10.1109/focs.2016.63openalex-snapshot
Testing Assignments to Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1109/focs.2017.37openalex-snapshot
A Dichotomy Theorem for Nonuniform CSPs
inferred← citeshttps://doi.org/10.1109/ismvl52857.2022.00019openalex-snapshot
Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep
inferred← citeshttps://doi.org/10.1109/lics52264.2021.9470670openalex-snapshot
Constraint Satisfaction Problems over Finite Structures
inferred← citeshttps://doi.org/10.1137/1.9781611977073.46openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1137/1.9781611977073.48openalex-snapshot
Promise Constraint Satisfaction and Width
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch25openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
inferred← citeshttps://doi.org/10.1137/130915479openalex-snapshot
Robustly Solvable Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/16m1079245openalex-snapshot
The Power of Sherali--Adams Relaxations for General-Valued CSPs
inferred← citeshttps://doi.org/10.1137/18m117577xopenalex-snapshot
Solving CSPs Using Weak Local Consistency
inferred← citeshttps://doi.org/10.1137/18m121085xopenalex-snapshot
Constant-Query Testability of Assignments to Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/22m1476435openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1137/22m1538934openalex-snapshot
Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough
inferred← citeshttps://doi.org/10.1137/24m1691594openalex-snapshot
Approximate Graph Coloring and the Crystal with a Hollow Shadow
inferred← citeshttps://doi.org/10.1145/2677161.2677165openalex-snapshot
Constraint satisfaction problem and universal algebra
inferred← citeshttps://doi.org/10.1145/2933575.2933604openalex-snapshot
Graphs of relational structures
inferred← citeshttps://doi.org/10.1145/2933575.2934510openalex-snapshot
Weak consistency notions for all the CSPs of bounded width
inferred← citeshttps://doi.org/10.1145/3134757openalex-snapshot
Asking the Metaquestions in Constraint Tractability
inferred← citeshttps://doi.org/10.1145/3292048.3292050openalex-snapshot
Constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/3373718.3394781openalex-snapshot
On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width
inferred← citeshttps://doi.org/10.1145/3564246.3585112openalex-snapshot
Approximate Graph Colouring and the Hollow Shadow
inferred← citeshttps://doi.org/10.1145/3756323openalex-snapshot
The Sherali–Adams and Weisfeiler–Leman Hierarchies in (Promise Valued) Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1145/3799414openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
inferred← citeshttps://doi.org/10.1609/aaai.v30i1.10432openalex-snapshot
The Meta-Problem for Conservative Mal'tsev Constraints
inferred← citeshttps://doi.org/10.23638/lmcs-15(2:15)2019openalex-snapshot
Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
inferred← citeshttps://doi.org/10.32920/23459144openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.32920/23459144.v1openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.138openalex-snapshot
Smooth Approximations and Relational Width Collapses
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2021.27openalex-snapshot
Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1604.07063openalex-snapshot
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
inferred← citeshttps://doi.org/10.48550/arxiv.1605.00565openalex-snapshot
Weaker consistency notions for all the CSPs of bounded width
inferred← citeshttps://doi.org/10.48550/arxiv.1909.05901openalex-snapshot
Examples, counterexamples, and structure in bounded width algebras
inferred← citeshttps://doi.org/10.48550/arxiv.2006.11713openalex-snapshot
Graphs of relational structures: restricted types
inferred← citeshttps://doi.org/10.48550/arxiv.2007.09099openalex-snapshot
A dichotomy theorem for nonuniform CSPs simplified
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.