scientific article; zbMATH DE number 7359806
From MaRDI portal
Publication:4993594
DOI10.4230/DFU.Vol7.15301.1zbMath1482.68161MaRDI QIDQ4993594
Libor Barto, Ross Willard, Andrei A. Krokhin
Publication date: 15 June 2021
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational aspects of satisfiability (68R07)
Related Items (38)
On a stronger reconstruction notion for monoids and clones ⋮ 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) ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ The Gumm level equals the Alvin level in congruence distributive varieties ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Proof Complexity Meets Algebra ⋮ Unnamed Item ⋮ Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Testing for a semilattice term ⋮ DECIDING SOME MALTSEV CONDITIONS IN FINITE IDEMPOTENT ALGEBRAS ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ Constraint satisfaction problems over semilattice block Mal'tsev algebras ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Loop conditions ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Loop conditions for strongly connected digraphs ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ The local loop lemma ⋮ Accessible set functors are universal ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Unnamed Item ⋮ Testing the Complexity of a Valued CSP Language ⋮ Two-element structures modulo primitive positive constructability ⋮ The number of clones determined by disjunctions of unary relations ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮ The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
- Mal'tsev conditions, lack of absorption, and solvability.
- Maltsev families of varieties closed under join or Maltsev product
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Maltsev digraphs have a majority polymorphism
- Conservative constraint satisfaction re-revisited
- A new line of attack on the dichotomy conjecture
- CSP duality and trees of bounded pathwidth
- Bounded width problems and algebras
- Existence theorems for weakly symmetric operations
- Universal algebra and hardness results for constraint satisfaction problems
- Affine systems of equations and counting infinitary logic
- The complexity of satisfiability problems: Refining Schaefer's theorem
- CD(4) has bounded width
- The method of forced enumeration for nondeterministic automata
- On the complexity of H-coloring
- List homomorphisms to reflexive graphs
- Polynomial interpolation and the Chinese remainder theorem for algebraic systems
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Conjunctive-query containment and constraint satisfaction
- Finitely related algebras in congruence modular varieties have few subpowers
- The wonderland of reflections
- Isolation, matching, and counting uniform and nonuniform upper bounds
- List homomorphisms and circular arc graphs
- On \(n\)-permutable congruences
- Characterizations of several Maltsev conditions.
- Majority constraints have bounded pathwidth duality
- Combinatorial problems raised from 2-semilattices
- Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
- Closed systems of functions and predicates
- Robustly Solvable Constraint Satisfaction Problems
- The collapse of the bounded width hierarchy
- Linear programming, width-1 CSPs, and robust satisfaction
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- Meditations on Quantified Constraint Satisfaction
- Complexity of conservative constraint satisfaction problems
- Robust Satisfiability for CSPs
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- The Complexity of Finite-Valued CSPs
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- A finer reduction of constraint problems to digraphs
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- Varieties with few subalgebras of powers
- Congruence Distributivity Implies Bounded Width
- Undirected connectivity in log-space
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- Nondeterministic Space is Closed under Complementation
- Structure and importance of logspace-MOD class
- The structure of finite algebras
- On the Structure of Polynomial Time Reducibility
- Varieties Obeying Homotopy Laws
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Correlation Decay and Tractability of CSPs.
- Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
- The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
- Weak consistency notions for all the CSPs of bounded width
- Graphs of relational structures
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- Making Nondeterminism Unambiguous
- Constraint Satisfaction Problems over Numeric Domains
- Constraint Satisfaction Problems of Bounded Width
- The Power of Linear Programming for General-Valued CSPs
- Complexity and polymorphisms for digraph constraint problems under some basic constructions
- Linear Datalog and Bounded Path Duality of Relational Structures
- Generalized Majority-Minority Operations are Tractable
- On tractability and congruence distributivity
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- Towards a Characterization of Constant-Factor Approximable Min CSPs
- $(2+\varepsilon)$-Sat Is NP-hard
- New hardness results for graph and hypergraph colorings
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of the counting constraint satisfaction problem
- Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
- An Algebraic Theory of Complexity for Discrete Optimization
- The complexity of satisfiability problems
- Some optimal inapproximability results
- A Simple Algorithm for Mal'tsev Constraints
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dualities for Constraint Satisfaction Problems
- Constraint Satisfaction Problems with Infinite Templates
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
This page was built for publication:
