On the public citation graph
The Complexity of Promise SAT on Non-Boolean Domains
0 signed · 42 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.1002/malq.19670130104openalex-snapshot
The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
inferredcites →https://doi.org/10.1007/s00493-005-0032-4openalex-snapshot
The Hardness of 3-Uniform Hypergraph Coloring
inferredcites →https://doi.org/10.1007/s00493-016-3383-0openalex-snapshot
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
inferredcites →https://doi.org/10.1016/j.jcss.2010.04.003openalex-snapshot
Constraint satisfaction with succinctly specified relations
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.1991.185365openalex-snapshot
On selecting a satisfying truth assignment
inferredcites →https://doi.org/10.1137/050635900openalex-snapshot
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains
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.9781611975482.28openalex-snapshot
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
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.90openalex-snapshot
Improved Inapproximability of Rainbow Coloring
inferredcites →https://doi.org/10.1137/19m127731xopenalex-snapshot
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
inferredcites →https://doi.org/10.1137/s0097539704443057openalex-snapshot
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
inferredcites →https://doi.org/10.1137/s0097539795280895openalex-snapshot
A Parallel Repetition Theorem
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/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/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.4230/dfu.vol7.15301.iopenalex-snapshot
Front Matter, Table of Contents, Preface, List of Authors
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175746openalex-snapshot
Boolean symmetric vs. functional PCSP dichotomy
inferred← citeshttps://doi.org/10.1137/1.9781611977073.46openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch25openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch86openalex-snapshot
Approximate Graph Colouring and Crystals
inferred← citeshttps://doi.org/10.1137/20m1378223openalex-snapshot
Topology and Adjunction in Promise Constraint Satisfaction
inferred← citeshttps://doi.org/10.1137/22m1476435openalex-snapshot
CLAP: A New Algorithm for Promise CSPs
inferred← citeshttps://doi.org/10.1137/24m1691594openalex-snapshot
Approximate Graph Coloring and the Crystal with a Hollow Shadow
inferred← citeshttps://doi.org/10.1145/3559736.3559740openalex-snapshot
An invitation to the promise constraint satisfaction problem
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/3570909openalex-snapshot
Linearly Ordered Colourings of Hypergraphs
inferred← citeshttps://doi.org/10.1145/3661814.3662068openalex-snapshot
Local consistency as a reduction between constraint satisfaction 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/3673655openalex-snapshot
On the Complexity of Symmetric vs. Functional PCSPs
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/3799414openalex-snapshot
Hierarchies of Minion Tests for PCSPs through Tensors
inferred← citeshttps://doi.org/10.1145/3840383openalex-snapshot
A Dichotomy for Maximum PCSPs on Graphs
inferred← citeshttps://doi.org/10.3390/electronics11152475openalex-snapshot
The Transition Phenomenon of (1,0)-d-Regular (k, s)-SAT
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.