The wonderland of reflections

DOI10.1007/s11856-017-1621-9zbMath1397.08002arXiv1510.04521OpenAlexW2963666051WikidataQ105697906 ScholiaQ105697906MaRDI QIDQ1709740

Michael Pinsker, Jakub Opršal, Libor Barto

Publication date: 6 April 2018

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityreflectioncoreclonerelational structureCSPpp-interpretable

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) Operations and polynomials in algebraic structures, primal algebras (08A40) Equational classes, universal algebra in model theory (03C05) Model theory of denumerable and separable structures (03C15) Categoricity and completeness of theories (03C35)

Related Items

CLAP: A New Algorithm for Promise CSPs, Topology and Adjunction in Promise Constraint Satisfaction, 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, Local–global property for G-invariant terms, Hardness of Network Satisfaction for Relation Algebras with Normal Representations, On the primeness of locally finite idempotent 3-permutability, A uniform Birkhoff theorem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The smallest hard trees, Uniform Birkhoff, The lattice of clones of self-dual operations collapsed, Constraint satisfaction problem: what makes the problem easy, Unnamed Item, Submaximal clones over a three-element set up to minor-equivalence, Binarisation for Valued Constraint Satisfaction Problems, Proof Complexity Meets Algebra, Constraint Satisfaction Problems over Numeric Domains, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, 𝜔-categorical structures avoiding height 1 identities, DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS, Reflection-closed varieties of multisorted algebras and minor identities, Reflections on and of minor-closed classes of multisorted operations, Solving equation systems in ω-categorical algebras, Reflections and powers of multisorted minions, Taylor's modularity conjecture and related problems for idempotent varieties, Pseudo‐loop conditions, A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP, Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, Unnamed Item, Accessible set functors are universal, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), Mal'tsev condition satisfaction problems for conditions which imply edge terms, Two-element structures modulo primitive positive constructability, A Dichotomy for First-Order Reducts of Unary Structures, PROJECTIVE CLONE HOMOMORPHISMS, CORES OVER RAMSEY STRUCTURES, Unnamed Item, Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}), Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance constraint satisfaction problems
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Bounded width problems and algebras
• Uniform Birkhoff
• On \(n\)-permutable congruences
• Taylor's modularity conjecture holds for linear idempotent varieties.
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• 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 Problems Solvable by Local Consistency Methods
• The lattice of interpretability types of varieties
• Constraint Satisfaction with Countable Homogeneous Templates
• Constraint Satisfaction Problems over the Integers with Successor
• The complexity of temporal constraint satisfaction problems
• On Malcev conditions
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• PROJECTIVE CLONE HOMOMORPHISMS
• AUTOMORPHISM GROUPS OF SQUARES AND OF FREE ALGEBRAS
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• Decidability of Definability
• Idempotent n -permutable varieties
• Topological Birkhoff