No label defined (Q4993594)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7359806

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7359806

Statements

scholarly article

0 references

0 references

Andrei A. Krokhin

0 references

0 references

publication date

15 June 2021

0 references

zbMATH Keywords

constraint satisfaction

0 references

complexity

0 references

universal algebra

0 references

polymorphism

0 references

MaRDI profile type

MaRDI publication profile

0 references

The complexity of satisfiability problems: Refining Schaefer's theorem

0 references

Isolation, matching, and counting uniform and nonuniform upper bounds

0 references

Computational Complexity

0 references

Affine systems of equations and counting infinitary logic

0 references

$(2+\varepsilon)$-Sat Is NP-hard

0 references

Polynomial interpolation and the Chinese remainder theorem for algebraic systems

0 references

Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms

0 references

Finitely related algebras in congruence modular varieties have few subpowers

0 references

The collapse of the bounded width hierarchy

0 references

Congruence Distributivity Implies Bounded Width

0 references

Constraint Satisfaction Problems of Bounded Width

0 references

Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem

0 references

Constraint Satisfaction Problems Solvable by Local Consistency Methods

0 references

Robustly Solvable Constraint Satisfaction Problems

0 references

0 references

The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)

0 references

Mal'tsev conditions, lack of absorption, and solvability.

0 references

Near Unanimity Constraints Have Bounded Pathwidth Duality

0 references

The wonderland of reflections

0 references

The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems

0 references

0 references

Varieties with few subalgebras of powers

0 references

Constraint Satisfaction Problems with Infinite Templates

0 references

Constraint Satisfaction Problems over Numeric Domains

0 references

0 references

New hardness results for graph and hypergraph colorings

0 references

0 references

Correlation Decay and Tractability of CSPs.

0 references

A Simple Algorithm for Mal'tsev Constraints

0 references

Classifying the Complexity of Constraints Using Finite Algebras

0 references

Combinatorial problems raised from 2-semilattices

0 references

A dichotomy theorem for constraint satisfaction problems on a 3-element set

0 references

Complexity of conservative constraint satisfaction problems

0 references

The complexity of the counting constraint satisfaction problem

0 references

Conservative constraint satisfaction re-revisited

0 references

Graphs of relational structures

0 references

0 references

Dualities for Constraint Satisfaction Problems

0 references

A finer reduction of constraint problems to digraphs

0 references

Structure and importance of logspace-MOD class

0 references

CSP duality and trees of bounded pathwidth

0 references

CD(4) has bounded width

0 references

Meditations on Quantified Constraint Satisfaction

0 references

An Algebraic Theory of Complexity for Discrete Optimization

0 references

Linear Datalog and Bounded Path Duality of Relational Structures

0 references

Generalized Majority-Minority Operations are Tractable

0 references

Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy

0 references

Robust algorithms with polynomial loss for near-unanimity CSPs

0 references

Majority constraints have bounded pathwidth duality

0 references

Robust Satisfiability for CSPs

0 references

Towards a Characterization of Constant-Factor Approximable Min CSPs

0 references

0 references

An Effective Dichotomy for the Counting Constraint Satisfaction Problem

0 references

List homomorphisms to reflexive graphs

0 references

List homomorphisms and circular arc graphs

0 references

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

0 references

Maltsev families of varieties closed under join or Maltsev product

0 references

Closed systems of functions and predicates

0 references

On \(n\)-permutable congruences

0 references

Some optimal inapproximability results

0 references

0 references

On the complexity of H-coloring

0 references

0 references

The structure of finite algebras

0 references

Tractability and Learnability Arising from Algebras with Few Subpowers

0 references

Nondeterministic Space is Closed under Complementation

0 references

Complexity and polymorphisms for digraph constraint problems under some basic constructions

0 references

On the algebraic structure of combinatorial problems

0 references

Constraints, consistency and closure

0 references

Closure properties of constraints

0 references

Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties

0 references

Maltsev digraphs have a majority polymorphism

0 references

0 references

Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.

0 references

On tractability and congruence distributivity

0 references

Conjunctive-query containment and constraint satisfaction

0 references

The Power of Linear Programming for General-Valued CSPs

0 references

Weak consistency notions for all the CSPs of bounded width

0 references

Characterizations of several Maltsev conditions.

0 references

Linear programming, width-1 CSPs, and robust satisfaction

0 references

A new line of attack on the dichotomy conjecture

0 references

On the Structure of Polynomial Time Reducibility

0 references

Universal algebra and hardness results for constraint satisfaction problems

0 references

OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT

0 references

TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS

0 references

Bounded width problems and algebras

0 references

Existence theorems for weakly symmetric operations

0 references

Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries

0 references

0 references

The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

0 references

Undirected connectivity in log-space

0 references

Making Nondeterminism Unambiguous

0 references

0 references

The complexity of satisfiability problems

0 references

A strong Mal'cev condition for locally finite varieties omitting the unary type

0 references

The method of forced enumeration for nondeterministic automata

0 references

Varieties Obeying Homotopy Laws

0 references

The Complexity of Finite-Valued CSPs

0 references

Identifiers

zbMATH Open document ID

0 references

10.4230/DFU.Vol7.15301.1

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4993594

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q4993594&oldid=36691112"