On the public citation graph

Tractability and Learnability Arising from Algebras with Few Subpowers

0 signed · 127 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.1006/jcss.1995.1026openalex-snapshot
When Won′t Membership Queries Help?
inferredcites →https://doi.org/10.1007/s00012-009-2113-5openalex-snapshot
CD(4) has bounded width
inferredcites →https://doi.org/10.1007/s10472-005-7031-4openalex-snapshot
The expressive rate of constraints
inferredcites →https://doi.org/10.1016/j.cosrev.2008.10.003openalex-snapshot
Colouring, constraint satisfaction, and complexity
inferredcites →https://doi.org/10.1016/j.tcs.2007.03.039openalex-snapshot
Learning intersection-closed classes with signatures
inferredcites →https://doi.org/10.1016/s0004-3702(98)00022-8openalex-snapshot
Constraints, consistency and closure
inferredcites →https://doi.org/10.1016/s0304-3975(03)00342-6openalex-snapshot
Learnability of quantified formulas
inferredcites →https://doi.org/10.1016/s0304-3975(97)00230-2openalex-snapshot
On the algebraic structure of combinatorial problems
inferredcites →https://doi.org/10.1090/s0002-9947-09-04874-0openalex-snapshot
Varieties with few subalgebras of powers
inferredcites →https://doi.org/10.1137/050628957openalex-snapshot
A Simple Algorithm for Mal'tsev Constraints
inferredcites →https://doi.org/10.1137/070708093openalex-snapshot
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
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/s0218196709004956openalex-snapshot
ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
inferredcites →https://doi.org/10.1145/1120582.1120584openalex-snapshot
A dichotomy theorem for constraint satisfaction problems on a 3-element set
inferredcites →https://doi.org/10.2178/jsl/1245158096openalex-snapshot
The existence of a near-unanimity term in a finite algebra is decidable

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-031-24117-8_18openalex-snapshot
Constraint Satisfaction, Graph Isomorphism, and the Pebbling Comonad
inferred← citeshttps://doi.org/10.1007/978-3-319-10428-7_18openalex-snapshot
On Backdoors to Tractable Constraint Languages
inferred← citeshttps://doi.org/10.1007/978-3-319-11478-1_10openalex-snapshot
Algebra and Coalgebra Objects in Categories, and Functors Having Adjoints
inferred← citeshttps://doi.org/10.1007/978-3-319-66158-2_10openalex-snapshot
All or Nothing: Toward a Promise Problem Dichotomy for Constraint Problems
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-540-70575-8_53openalex-snapshot
The Complexity of the Counting Constraint Satisfaction Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_26openalex-snapshot
On the CSP Dichotomy Conjecture
inferred← citeshttps://doi.org/10.1007/978-3-642-22012-8_27openalex-snapshot
Generic Expression Hardness Results for Primitive Positive Formula Comparison
inferred← citeshttps://doi.org/10.1007/978-3-642-29485-3_4openalex-snapshot
Meditations on Quantified Constraint Satisfaction
inferred← citeshttps://doi.org/10.1007/978-3-642-33974-5_1openalex-snapshot
Background
inferred← citeshttps://doi.org/10.1007/978-3-642-33974-5_6openalex-snapshot
Tractable Languages
inferred← citeshttps://doi.org/10.1007/978-3-642-40627-0_17openalex-snapshot
On the Reduction of the CSP Dichotomy Conjecture to Digraphs
inferred← citeshttps://doi.org/10.1007/s00012-014-0308-xopenalex-snapshot
An algebraic hardness criterion for surjective constraint satisfaction
inferred← citeshttps://doi.org/10.1007/s00012-015-0323-6openalex-snapshot
Commutative idempotent groupoids and the constraint satisfaction problem
inferred← citeshttps://doi.org/10.1007/s00012-015-0338-zopenalex-snapshot
Mal’tsev conditions, lack of absorption, and solvability
inferred← citeshttps://doi.org/10.1007/s00012-016-0388-xopenalex-snapshot
Dualities and algebras with a near-unanimity term
inferred← citeshttps://doi.org/10.1007/s00012-017-0476-6openalex-snapshot
Cube term blockers without finiteness
inferred← citeshttps://doi.org/10.1007/s00012-020-00700-7openalex-snapshot
Existence of cube terms in finite algebras
inferred← citeshttps://doi.org/10.1007/s00012-023-00832-6openalex-snapshot
Vaughan-Lee’s nilpotent loop of size 12 is finitely based
inferred← citeshttps://doi.org/10.1007/s00012-024-00865-5openalex-snapshot
Graphs of finite algebras: edges, and connectivity
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/s00453-018-0498-2openalex-snapshot
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns
inferred← citeshttps://doi.org/10.1007/s10601-015-9198-6openalex-snapshot
Tractability in constraint satisfaction problems: a survey
inferred← citeshttps://doi.org/10.1007/s11083-011-9232-2openalex-snapshot
Finitely Related Clones and Algebras with Cube Terms
inferred← citeshttps://doi.org/10.1016/j.disc.2015.06.024openalex-snapshot
Dichotomy for finite tournaments of mixed-type
inferred← citeshttps://doi.org/10.1016/j.ejc.2015.07.011openalex-snapshot
A new line of attack on the dichotomy conjecture
inferred← citeshttps://doi.org/10.1016/j.ic.2012.10.008openalex-snapshot
Generic expression hardness results for primitive positive formula comparison
inferred← citeshttps://doi.org/10.1016/j.ic.2019.104437openalex-snapshot
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras
inferred← citeshttps://doi.org/10.1016/j.jalgebra.2017.06.034openalex-snapshot
The subpower membership problem for bands
inferred← citeshttps://doi.org/10.1016/j.jcss.2015.07.004openalex-snapshot
Conservative constraint satisfaction re-revisited
inferred← citeshttps://doi.org/10.1016/j.jcss.2016.10.007openalex-snapshot
Backdoors into heterogeneous classes of SAT and CSP
inferred← citeshttps://doi.org/10.1017/9781107337534openalex-snapshot
Complexity of Infinite-Domain Constraint Satisfaction
inferred← citeshttps://doi.org/10.1017/cbo9781139177801.005openalex-snapshot
Tractable Valued Constraints
inferred← citeshttps://doi.org/10.1017/s1446788718000010openalex-snapshot
ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
inferred← citeshttps://doi.org/10.1093/logcom/exr039openalex-snapshot
Arc consistency and friends
inferred← citeshttps://doi.org/10.1093/logcom/exw005openalex-snapshot
The power of primitive positive definitions with polynomially many variables
inferred← citeshttps://doi.org/10.1109/focs.2012.25openalex-snapshot
The Power of Linear Programming for Valued CSPs
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/focs.2017.38openalex-snapshot
A Proof of CSP Dichotomy Conjecture
inferred← citeshttps://doi.org/10.1109/focs.2018.00031openalex-snapshot
The Complexity of General-Valued CSPs Seen from the Other Side
inferred← citeshttps://doi.org/10.1109/ismvl.2012.46openalex-snapshot
Counting Predicates, Subset Surjective Functions, and Counting CSPs
inferred← citeshttps://doi.org/10.1109/ismvl.2016.10openalex-snapshot
Minimal Weighted Clones with Boolean Support
inferred← citeshttps://doi.org/10.1109/lics.2009.38openalex-snapshot
The Complexity of Global Cardinality Constraints
inferred← citeshttps://doi.org/10.1109/lics.2012.32openalex-snapshot
An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction
inferred← citeshttps://doi.org/10.1109/lics.2017.8005116openalex-snapshot
The complexity of minimal inference problem for conservative constraint languages
inferred← citeshttps://doi.org/10.1109/lics.2017.8005149openalex-snapshot
Constraint satisfaction problems over semilattice block Mal'tsev algebras
inferred← citeshttps://doi.org/10.1109/lics.2019.8785678openalex-snapshot
A short story of the CSP dichotomy conjecture
inferred← citeshttps://doi.org/10.1109/lics52264.2021.9470557openalex-snapshot
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
inferred← citeshttps://doi.org/10.1137/080743238openalex-snapshot
Congruence Distributivity Implies Bounded Width
inferred← citeshttps://doi.org/10.1137/1.9781611977073.46openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1137/130945648openalex-snapshot
The Power of Linear Programming for General-Valued CSPs
inferred← citeshttps://doi.org/10.1137/140990346openalex-snapshot
Necessary Conditions for Tractability of Valued CSPs
inferred← citeshttps://doi.org/10.1137/16m1088107openalex-snapshot
Binarisation for Valued Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/18m121085xopenalex-snapshot
Constant-Query Testability of Assignments to Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/18m1220194openalex-snapshot
Satisfiability in MultiValued Circuits
inferred← citeshttps://doi.org/10.1137/19m1250121openalex-snapshot
The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
inferred← citeshttps://doi.org/10.1137/22m1476435openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1142/s0218196716500600openalex-snapshot
Complexity and polymorphisms for digraph constraint problems under some basic constructions
inferred← citeshttps://doi.org/10.1142/s0218196716500612openalex-snapshot
The subpower membership problem for semigroups
inferred← citeshttps://doi.org/10.1142/s0218196716500685openalex-snapshot
On finite Taylor algebras
inferred← citeshttps://doi.org/10.1142/s0218196723500017openalex-snapshot
Between an n-ary and an n + 1-ary near-unanimity term
inferred← citeshttps://doi.org/10.1145/2450142.2450146openalex-snapshot
The complexity of conservative valued CSPs
inferred← citeshttps://doi.org/10.1145/2488608.2488697openalex-snapshot
The complexity of finite-valued CSPs
inferred← citeshttps://doi.org/10.1145/2933575.2933587openalex-snapshot
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
inferred← citeshttps://doi.org/10.1145/2933575.2933604openalex-snapshot
Graphs of relational structures
inferred← citeshttps://doi.org/10.1145/2974019openalex-snapshot
The Complexity of Finite-Valued CSPs
inferred← citeshttps://doi.org/10.1145/3134757openalex-snapshot
Asking the Metaquestions in Constraint Tractability
inferred← citeshttps://doi.org/10.1145/3209108.3209173openalex-snapshot
Satisfiability in multi-valued circuits
inferred← citeshttps://doi.org/10.1145/3265985openalex-snapshot
Proof Complexity Meets Algebra
inferred← citeshttps://doi.org/10.1145/3292048.3292050openalex-snapshot
Constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/3301410openalex-snapshot
The Complexity of Minimal Inference Problem for Conservative Constraint Languages
inferred← citeshttps://doi.org/10.1145/3313276.3316300openalex-snapshot
Algebraic approach to promise constraint satisfaction
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/3389411openalex-snapshot
Sparsification of SAT and CSP Problems via Tractable Extensions
inferred← citeshttps://doi.org/10.1145/3457606openalex-snapshot
Algebraic Approach to Promise Constraint Satisfaction
inferred← citeshttps://doi.org/10.1145/3492336openalex-snapshot
The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
inferred← citeshttps://doi.org/10.1145/3559736.3559740openalex-snapshot
An invitation to the promise constraint satisfaction problem
inferred← citeshttps://doi.org/10.1145/3661814.3662076openalex-snapshot
Algebraic Approach to Approximation
inferred← citeshttps://doi.org/10.1515/ms-2024-0022openalex-snapshot
Exact-m-majority terms
inferred← citeshttps://doi.org/10.1609/aaai.v29i1.9749openalex-snapshot
Binarisation via Dualisation for Valued Constraints
inferred← citeshttps://doi.org/10.1609/aaai.v30i1.10432openalex-snapshot
The Meta-Problem for Conservative Mal'tsev Constraints
inferred← citeshttps://doi.org/10.1609/aaai.v34i02.5499openalex-snapshot
Chain Length and CSPs Learnable with Few Queries
inferred← citeshttps://doi.org/10.1613/jair.3747openalex-snapshot
Tractable Set Constraints
inferred← citeshttps://doi.org/10.1613/jair.5260openalex-snapshot
A Model-Theoretic View on Qualitative Constraint Reasoning
inferred← citeshttps://doi.org/10.2168/lmcs-11(4:18)2015openalex-snapshot
A finer reduction of constraint problems to digraphs
inferred← citeshttps://doi.org/10.2168/lmcs-9(1:15)2013openalex-snapshot
An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction
inferred← citeshttps://doi.org/10.2298/fil2313083popenalex-snapshot
SMB algebras I: On the variety of SMB algebras
inferred← citeshttps://doi.org/10.23638/lmcs-13(4:26)2017openalex-snapshot
The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns
inferred← citeshttps://doi.org/10.23638/lmcs-15(1:11)2019openalex-snapshot
The Subpower Membership Problem for Finite Algebras with Cube Terms
inferred← citeshttps://doi.org/10.31274/etd-180810-3421openalex-snapshot
Commutative, idempotent groupoids and the constraint satisfaction problem
inferred← citeshttps://doi.org/10.32920/21482265openalex-snapshot
A Finer Reduction of Constraint Problems to Digraphs
inferred← citeshttps://doi.org/10.32920/21482265.v1openalex-snapshot
A Finer Reduction of Constraint Problems to Digraphs
inferred← citeshttps://doi.org/10.32920/ryerson.14653140openalex-snapshot
Constraint satisfaction problems in the logic LFP +rank
inferred← citeshttps://doi.org/10.32920/ryerson.14653140.v1openalex-snapshot
Constraint satisfaction problems in the logic LFP +rank
inferred← citeshttps://doi.org/10.32920/ryerson.14653842openalex-snapshot
Constraint Satisfaction Problems and Their Reduction to Directed Graphs
inferred← citeshttps://doi.org/10.32920/ryerson.14653842.v1openalex-snapshot
Constraint Satisfaction Problems and Their Reduction to Directed Graphs
inferred← citeshttps://doi.org/10.3384/diss.diva-122827openalex-snapshot
Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications
inferred← citeshttps://doi.org/10.4230/lipics.csl.2013.149openalex-snapshot
Descriptive complexity of approximate counting CSPs
inferred← citeshttps://doi.org/10.4230/lipics.csl.2017.42openalex-snapshot
An Algebraic Approach to Valued Constraint Satisfaction
inferred← citeshttps://doi.org/10.46298/lmcs-18(1:12)2022openalex-snapshot
Universal Algebraic Methods for Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.46298/theoretics.24.14openalex-snapshot
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
inferred← citeshttps://doi.org/10.48550/arxiv.1205.5745openalex-snapshot
Generic Expression Hardness Results for Primitive Positive Formula Comparison
inferred← citeshttps://doi.org/10.48550/arxiv.1210.3344openalex-snapshot
Galois correspondence for counting quantifiers
inferred← citeshttps://doi.org/10.48550/arxiv.1404.3675openalex-snapshot
On Backdoors To Tractable Constraint Languages
inferred← citeshttps://doi.org/10.48550/arxiv.1609.03943openalex-snapshot
A Constraint Satisfaction Problem Algorithm for Certain 2-Semilattice-over-Edge Algebras
inferred← citeshttps://doi.org/10.48550/arxiv.2006.10239openalex-snapshot
Local structure of idempotent algebras II
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
inferred← citeshttps://doi.org/10.5591/978-1-57735-516-8/ijcai11-093openalex-snapshot
Tractable set constraints
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.