Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)

DOI10.1137/18M1216213zbMath1432.68169arXiv1909.06201WikidataQ123195905 ScholiaQ123195905MaRDI QIDQ5222129

Libor Barto, Michael Pinsker

Publication date: 1 April 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.06201

zbMATH Keywords

polymorphismconstraint satisfaction problempointwise convergence topologydichotomy conjectureSiggers identityomega-categorical structure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Equational classes, universal algebra in model theory (03C05) Categoricity and completeness of theories (03C35) Parameterized complexity, tractability and kernelization (68Q27) Computational aspects of satisfiability (68R07)

Related Items (11)

CLAP: A New Algorithm for Promise CSPs ⋮ Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Unnamed Item ⋮ Pseudo‐loop conditions ⋮ A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP ⋮ Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures ⋮ Constraint Satisfaction Problems for Reducts of Homogeneous Graphs ⋮ PROJECTIVE CLONE HOMOMORPHISMS ⋮ CORES OVER RAMSEY STRUCTURES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• \(H\)-coloring dichotomy revisited
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• On the algebraic structure of combinatorial problems
• A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
• Uniform Birkhoff
• The wonderland of reflections
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Closed systems of functions and predicates
• THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
• Schaefer's Theorem for Graphs
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Reconstructing the topology of clones
• Reducts of Ramsey structures
• Constraint Satisfaction with Countable Homogeneous Templates
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The structure of finite algebras
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The weakest nontrivial idempotent equations
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• A Dichotomy for First-Order Reducts of Unary Structures
• Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
• PROJECTIVE CLONE HOMOMORPHISMS
• A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• The Complexity of Phylogeny Constraint Satisfaction Problems
• Topological Birkhoff

This page was built for publication: Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)