On the public citation graph
CLAP: A New Algorithm for Promise CSPs
0 signed · 84 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/978-3-662-47672-7_21openalex-snapshot
Constraint Satisfaction Problems over the Integers with Successor
inferredcites →https://doi.org/10.1007/s00493-005-0032-4openalex-snapshot
The Hardness of 3-Uniform Hypergraph Coloring
inferredcites →https://doi.org/10.1007/s004930070013openalex-snapshot
On the Hardness of Approximating the Chromatic Number
inferredcites →https://doi.org/10.1007/s11856-017-1621-9openalex-snapshot
The wonderland of reflections
inferredcites →https://doi.org/10.1016/0004-3702(77)90007-8openalex-snapshot
Consistency in networks of relations
inferredcites →https://doi.org/10.1016/0095-8956(90)90132-jopenalex-snapshot
On the complexity of H-coloring
inferredcites →https://doi.org/10.1016/j.artint.2007.09.001openalex-snapshot
Theoretical analysis of singleton arc consistency and its extensions
inferredcites →https://doi.org/10.1016/j.ejc.2015.07.011openalex-snapshot
A new line of attack on the dichotomy conjecture
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/s0304-3975(97)00230-2openalex-snapshot
On the algebraic structure of combinatorial problems
inferredcites →https://doi.org/10.1023/b:cons.0000036045.82829.94openalex-snapshot
Tractable Decision for a Constraint Language Implies Tractable Search
inferredcites →https://doi.org/10.1090/s0002-9947-09-04874-0openalex-snapshot
Varieties with few subalgebras of powers
inferredcites →https://doi.org/10.1090/tran/8179openalex-snapshot
𝜔-categorical structures avoiding height 1 identities
inferredcites →https://doi.org/10.1093/logcom/exu070openalex-snapshot
The collapse of the bounded width hierarchy
inferredcites →https://doi.org/10.1109/focs.2015.80openalex-snapshot
The Complexity of General-Valued CSPs
inferredcites →https://doi.org/10.1109/focs.2017.37openalex-snapshot
A Dichotomy Theorem for Nonuniform CSPs
inferredcites →https://doi.org/10.1109/focs.2017.38openalex-snapshot
A Proof of CSP Dichotomy Conjecture
inferredcites →https://doi.org/10.1109/focs.2019.00076openalex-snapshot
The Complexity of 3-Colouring H-Colourable Graphs
inferredcites →https://doi.org/10.1109/sfcs.2001.959936openalex-snapshot
Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
inferredcites →https://doi.org/10.1137/050628957openalex-snapshot
A Simple Algorithm for Mal'tsev Constraints
inferredcites →https://doi.org/10.1137/090775646openalex-snapshot
Tractability and Learnability Arising from Algebras with Few Subpowers
inferredcites →https://doi.org/10.1137/1.9781611975031.117openalex-snapshot
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy
inferredcites →https://doi.org/10.1137/1.9781611975994.18openalex-snapshot
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
inferredcites →https://doi.org/10.1137/1.9781611975994.86openalex-snapshot
Improved hardness for H -colourings of G -colourable graphs
inferredcites →https://doi.org/10.1137/1.9781611975994.90openalex-snapshot
Improved Inapproximability of Rainbow Coloring
inferredcites →https://doi.org/10.1137/130915479openalex-snapshot
Robustly Solvable Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1137/130945648openalex-snapshot
The Power of Linear Programming for General-Valued CSPs
inferredcites →https://doi.org/10.1137/16m1079245openalex-snapshot
The Power of Sherali--Adams Relaxations for General-Valued CSPs
inferredcites →https://doi.org/10.1137/18m1163932openalex-snapshot
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
inferredcites →https://doi.org/10.1137/18m117577xopenalex-snapshot
Solving CSPs Using Weak Local Consistency
inferredcites →https://doi.org/10.1137/18m1216213openalex-snapshot
Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
inferredcites →https://doi.org/10.1137/19m128212xopenalex-snapshot
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
inferredcites →https://doi.org/10.1137/20m1312745openalex-snapshot
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
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.1137/s0895480100376794openalex-snapshot
On the Hardness of 4-Coloring a 3-Colorable Graph
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.1145/1132516.1132553openalex-snapshot
The PCP theorem by gap amplification
inferredcites →https://doi.org/10.1145/1374376.1374414openalex-snapshot
Optimal algorithms and inapproximability results for every CSP?
inferredcites →https://doi.org/10.1145/176584.176586openalex-snapshot
New approximation algorithms for graph coloring
inferredcites →https://doi.org/10.1145/2090236.2090274openalex-snapshot
Linear programming, width-1 CSPs, and robust satisfaction
inferredcites →https://doi.org/10.1145/2157.2158openalex-snapshot
Improving the performance guarantee for approximate graph coloring
inferredcites →https://doi.org/10.1145/2556646openalex-snapshot
Constraint Satisfaction Problems Solvable by Local Consistency Methods
inferredcites →https://doi.org/10.1145/263867.263489openalex-snapshot
Closure properties of constraints
inferredcites →https://doi.org/10.1145/273865.273901openalex-snapshot
Probabilistic checking of proofs
inferredcites →https://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferredcites →https://doi.org/10.1145/2933575.2934510openalex-snapshot
Weak consistency notions for all the CSPs of bounded width
inferredcites →https://doi.org/10.1145/3154832openalex-snapshot
Discrete Temporal Constraint Satisfaction Problems
inferredcites →https://doi.org/10.1145/3201777openalex-snapshot
The Limits of SDP Relaxations for General-Valued CSPs
inferredcites →https://doi.org/10.1145/321921.321926openalex-snapshot
The Complexity of Near-Optimal Graph Coloring
inferredcites →https://doi.org/10.1145/3313276.3316300openalex-snapshot
Algebraic approach to promise constraint satisfaction
inferredcites →https://doi.org/10.1145/3457606openalex-snapshot
Algebraic Approach to Promise Constraint Satisfaction
inferredcites →https://doi.org/10.1145/3470867openalex-snapshot
The Complexity of Promise SAT on Non-Boolean Domains
inferredcites →https://doi.org/10.1145/509907.510017openalex-snapshot
On the power of unique 2-prover 1-round games
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.2307/2267373openalex-snapshot
A. Malcev. Untersuchungen aus dem Gebiete der mathematischen Logik. Matématičéskij sbornik, n.s. vol. 1 (1936), pp. 323–336.
inferredcites →https://doi.org/10.4230/dfu.vol7.15301.1openalex-snapshot
Polymorphisms, and How to Use Them
inferredcites →https://doi.org/10.4230/lipics.stacs.2021.10openalex-snapshot
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
inferredcites →https://doi.org/10.46298/theoretics.23.2openalex-snapshot
Conditional Dichotomy of Boolean Ordered Promise CSPs
inferredcites →https://doi.org/10.48550/arxiv.1605.00565openalex-snapshot
Weaker consistency notions for all the CSPs of bounded width
inferredcites →https://doi.org/10.5446/49341openalex-snapshot
The complexity of promise SAT on non-Boolean domains
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1016/j.jctb.2025.10.002openalex-snapshot
Quantum advantage and CSP complexity
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175746openalex-snapshot
Boolean symmetric vs. functional PCSP dichotomy
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch25openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
inferred← citeshttps://doi.org/10.1137/24m1691594openalex-snapshot
Approximate Graph Coloring and the Crystal with a Hollow Shadow
inferred← citeshttps://doi.org/10.1145/3564246.3585112openalex-snapshot
Approximate Graph Colouring and the Hollow Shadow
inferred← citeshttps://doi.org/10.1145/3564246.3585180openalex-snapshot
SDPs and Robust Satisfiability of Promise CSP
inferred← citeshttps://doi.org/10.1145/3618260.3649635openalex-snapshot
Semidefinite Programming and Linear Equations vs. Homomorphism Problems
inferred← citeshttps://doi.org/10.1145/3661814.3662069openalex-snapshot
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
inferred← citeshttps://doi.org/10.1145/3661814.3662072openalex-snapshot
Injective hardness condition for PCSPs
inferred← citeshttps://doi.org/10.1145/3661814.3662076openalex-snapshot
Algebraic Approach to Approximation
inferred← citeshttps://doi.org/10.1145/3661814.3662118openalex-snapshot
Quantum advantage and CSP complexity
inferred← citeshttps://doi.org/10.1145/3673655openalex-snapshot
On the Complexity of Symmetric vs. Functional PCSPs
inferred← citeshttps://doi.org/10.1145/3698106openalex-snapshot
Solving Promise Equations over Monoids and Groups
inferred← citeshttps://doi.org/10.1145/3717823.3718127openalex-snapshot
On Approximability of Satisfiable 𝑘-CSPs: V
inferred← citeshttps://doi.org/10.1145/3719007openalex-snapshot
1 -in- 3 vs . N ot -A ll -E qual : Dichotomy of a Broken Promise
inferred← citeshttps://doi.org/10.1145/3723141.3723145openalex-snapshot
The Quest towards Optimal Approximability of CSPs
inferred← citeshttps://doi.org/10.1145/3799414openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
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.