Dmitriy Zhuk

According to our database, Dmitriy Zhuk authored at least 30 papers between 2011 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2024

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

TheoretiCS, 2024

Π₂^P vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem.

Dmitriy Zhuk

CoRR, 2024

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations.

Dmitriy Zhuk

CoRR, 2024

∏₂^P vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem.

Dmitriy Zhuk

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

The lattice of clones of self-dual operations collapsed.

Manuel Bodirsky, Albert Vucaj, Dmitriy Zhuk

Int. J. Algebra Comput., June, 2023

The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation.

Catarina Carvalho, Florent R. Madelaine, Barnaby Martin, Dmitriy Zhuk

ACM Trans. Comput. Log., January, 2023

The complete classification for quantified equality constraints.

Dmitriy Zhuk, Barnaby Martin, Michal Wrona

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Small Promise CSPs that reduce to large CSPs.

Alexandr Kazda, Peter Mayr, Dmitriy Zhuk

Log. Methods Comput. Sci., 2022

QCSP Monsters and the Demise of the Chen Conjecture.

Dmitriy Zhuk, Barnaby Martin

J. ACM, 2022

2021

Strong Subalgebras and the Constraint Satisfaction Problem.

Dmitriy Zhuk

J. Multiple Valued Log. Soft Comput., 2021

The complexity of the Quantified CSP having the polynomially generated powers property.

Dmitriy Zhuk

CoRR, 2021

Small PCSPs that reduce to large CSPs.

Alexandr Kazda, Peter Mayr, Dmitriy Zhuk

CoRR, 2021

The complete classification for quantified equality constraints.

Dmitriy Zhuk, Barnaby Martin

CoRR, 2021

No-Rainbow Problem and the Surjective Constraint Satisfaction Problem.

Dmitriy Zhuk

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP.

Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

A Proof of the CSP Dichotomy Conjecture.

Dmitriy Zhuk

J. ACM, 2020

No-Rainbow Problem is NP-Hard.

Dmitriy Zhuk

CoRR, 2020

2019

The Number of Clones Determined by Disjunctions of Unary Relations.

Mike Behrisch, Edith Vargas-García, Dmitriy Zhuk

Theory Comput. Syst., 2019

The size of generating sets of powers.

Dmitriy Zhuk

J. Comb. Theory A, 2019

Existence of cube terms in finite finitely generated clones.

Alexandr Kazda, Dmitriy Zhuk

CoRR, 2019

Deciding the existence of minority terms.

Alexandr Kazda, Jakub Oprsal, Matt Valeriote, Dmitriy Zhuk

CoRR, 2019

2018

A modifiction of the CSP algorithm for infinite languages.

Dmitriy Zhuk

CoRR, 2018

2017

The complexity of quantified constraints.

Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

CoRR, 2017

The Complexity of Quantified Constraints Using the Algebraic Formulation.

Catarina Carvalho, Barnaby Martin, Dmitriy Zhuk

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

An Algorithm for Constraint Satisfaction Problem.

Dmitriy Zhuk

Proceedings of the 47th IEEE International Symposium on Multiple-Valued Logic, 2017

2015

The Lattice of All Clones of Self-Dual Functions in Three-Valued Logic.

Dmitriy Zhuk

J. Multiple Valued Log. Soft Comput., 2015

Switchability and collapsibility of Gap Algebras.

Barnaby Martin, Dmitriy Zhuk

CoRR, 2015

2014

On Key Relations Preserved by a Weak Near-Unanimity Function.

Dmitriy Zhuk

Proceedings of the IEEE 44th International Symposium on Multiple-Valued Logic, 2014

2013

On the Clones Containing a Near-Unanimity Function.

Dmitriy Zhuk, Stanislav Moiseev

Proceedings of the 43rd IEEE International Symposium on Multiple-Valued Logic, 2013

2011

The Lattice of the Clones of Self-Dual Functions in Three-Valued Logic.

Dmitriy Zhuk

Proceedings of the 41st IEEE International Symposium on Multiple-Valued Logic, 2011