default search action
Andrei A. Krokhin
◀ ▷ joint publications with coauthor community group 1
- > Home > Persons > Andrei A. Krokhin
Publications
- 2025
- [j41]Lorenzo Ciardo
, Marcin Kozik
1-in-3 vs. Not-All-Equal: Dichotomy of a Broken Promise. ACM Trans. Comput. Log. 26(2): 10:1-10:22 (2025) - 2024
- [j39]Víctor Dalmau
Functors on Relational Structures Which Admit Both Left and Right Adjoints. SIAM J. Discret. Math. 38(3): 2041-2068 (2024) - [c27]Lorenzo Ciardo
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. LICS 2024: 24:1-24:12 - 2023
- [j38]Andrei A. Krokhin
Topology and Adjunction in Promise Constraint Satisfaction. SIAM J. Comput. 52(1): 38-79 (2023) - [i27]Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin
On the complexity of the approximate hypergraph homomorphism problem. CoRR abs/2302.03456 (2023) - [i26]Víctor Dalmau, Andrei A. Krokhin
Functors on relational structures which admit both left and right adjoints. CoRR abs/2302.13657 (2023) - 2022
- [j37]Andrei A. Krokhin
An invitation to the promise constraint satisfaction problem. ACM SIGLOG News 9(3): 30-59 (2022) - [i25]Andrei A. Krokhin, Jakub Oprsal:
An invitation to the promise constraint satisfaction problem. CoRR abs/2208.13538 (2022) - [i24]Andrei A. Krokhin, Jakub Oprsal:
An Invitation to the Promise Constraint Satisfaction Problem. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j36]Libor Barto
Algebraic Approach to Promise Constraint Satisfaction. J. ACM 68(4): 28:1-28:66 (2021) - 2020
- [i23]Andrei A. Krokhin
Topology and adjunction in promise constraint satisfaction. CoRR abs/2003.11351 (2020) - [i22]Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and adjunction in promise constraint satisfaction. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [j35]Víctor Dalmau, Marcin Kozik
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. 48(6): 1763-1795 (2019) - [c26]Andrei A. Krokhin, Jakub Oprsal
The Complexity of 3-Colouring H-Colourable Graphs. FOCS 2019: 1227-1239 - [c25]Jakub Bulín
Algebraic approach to promise constraint satisfaction. STOC 2019: 602-613 - [i21]Andrei A. Krokhin, Jakub Oprsal:
The complexity of 3-colouring H-colourable graphs. CoRR abs/1904.03214 (2019) - [i20]Andrei A. Krokhin, Jakub Oprsal:
The complexity of 3-colouring H-colourable graphs. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j34]Víctor Dalmau, Andrei A. Krokhin
Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. Syst. Sci. 97: 14-27 (2018) - [i19]Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal:
Algebraic approach to promise constraint satisfaction. CoRR abs/1811.00970 (2018) - 2017
- [j33]Vladimir Kolmogorov, Andrei A. Krokhin
The Complexity of General-Valued CSPs. SIAM J. Comput. 46(3): 1087-1110 (2017) - [j32]David A. Cohen, Martin C. Cooper
Binarisation for Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. 31(4): 2279-2300 (2017) - [c24]Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev
Robust algorithms with polynomial loss for near-unanimity CSPs. SODA 2017: 340-357 - [p2]Libor Barto, Andrei A. Krokhin, Ross Willard:
Polymorphisms, and How to Use Them. The Constraint Satisfaction Problem 2017: 1-44 - [p1]Andrei A. Krokhin, Stanislav Zivný:
The Complexity of Valued CSPs. The Constraint Satisfaction Problem 2017: 233-266 - [e2]Andrei A. Krokhin, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-003-3 [contents] - [i18]Andrei A. Krokhin, Dániel Marx:
On the hardness of losing weight. CoRR abs/1711.03894 (2017) - 2016
- [j31]Catarina Carvalho
On algebras with many symmetric operations. Int. J. Algebra Comput. 26(5): 1019-1031 (2016) - [i17]Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal:
Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR abs/1607.04787 (2016) - [i16]David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný:
Binarisation for Valued Constraint Satisfaction Problems. CoRR abs/1608.01628 (2016) - [i15]Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran:
Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs. CoRR abs/1610.01019 (2016) - 2015
- [c23]Vladimir Kolmogorov, Andrei A. Krokhin
The Complexity of General-Valued CSPs. FOCS 2015: 1246-1258 - [c22]Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran:
Towards a Characterization of Constant-Factor Approximable Min CSPs. SODA 2015: 847-857 - [i14]Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek:
The Complexity of General-Valued CSPs. CoRR abs/1502.07327 (2015) - [i13]Robert Powell
A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs. CoRR abs/1507.01776 (2015) - [i12]Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports 5(7): 22-41 (2015) - 2014
- [j30]Peter Jeavons, Andrei A. Krokhin, Stanislav Zivný:
The Complexity of Valued Constraint Satisfaction. Bull. EATCS 113 (2014) - [j29]Anna Huber, Andrei A. Krokhin
Skew Bisubmodularity and Valued CSPs. SIAM J. Comput. 43(3): 1064-1084 (2014) - [j28]Anna Huber, Andrei A. Krokhin
Oracle Tractability of Skew Bisubmodular Functions. SIAM J. Discret. Math. 28(4): 1828-1837 (2014) - 2013
- [j27]Víctor Dalmau
Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Trans. Comput. Theory 5(4): 15:1-15:25 (2013) - [c21]Anna Huber, Andrei A. Krokhin, Robert Powell
Skew Bisubmodularity and Valued CSPs. SODA 2013: 1296-1305 - [i11]Anna Huber, Andrei A. Krokhin:
Oracle Tractability of Skew Bisubmodular Functions. CoRR abs/1308.6505 (2013) - 2012
- [j26]László Egri, Andrei A. Krokhin
The Complexity of the List Homomorphism Problem for Graphs. Theory Comput. Syst. 51(2): 143-178 (2012) - [j25]Andrei A. Krokhin
On the hardness of losing weight. ACM Trans. Algorithms 8(2): 19:1-19:18 (2012) - [i10]Johan Håstad, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports 2(11): 1-19 (2012) - 2011
- [j24]Catarina Carvalho
Two new homomorphism dualities and lattice operations. J. Log. Comput. 21(6): 1065-1092 (2011) - [i9]David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin:
A Maximal Tractable Class of Soft Constraints. CoRR abs/1107.0043 (2011) - 2010
- [j23]Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin
Retractions to Pseudoforests. SIAM J. Discret. Math. 24(1): 101-112 (2010) - [j22]Catarina Carvalho
CSP duality and trees of bounded pathwidth. Theor. Comput. Sci. 411(34-36): 3188-3208 (2010) - [c18]László Egri, Andrei A. Krokhin
The Complexity of the List Homomorphism Problem for Graphs. STACS 2010: 335-346 - 2009
- [j21]Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin
The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207(9): 923-944 (2009) - [j20]Peter Jonsson, Andrei A. Krokhin
Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. 410(38-40): 3856-3874 (2009) - [e1]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009. Dagstuhl Seminar Proceedings 09441, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i8]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i7]Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin:
09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability 2009 - [i6]László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson:
The complexity of the list homomorphism problem for graphs. CoRR abs/0912.3802 (2009) - 2008
- [j19]Víctor Dalmau
Retractions onto series-parallel posets. Discret. Math. 308(11): 2104-2114 (2008) - [j18]Víctor Dalmau
Majority constraints have bounded pathwidth duality. Eur. J. Comb. 29(4): 821-837 (2008) - [j17]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The approximability of MAX CSP with fixed-value constraints. J. ACM 55(4): 16:1-16:37 (2008) - [j16]Peter Jonsson, Andrei A. Krokhin
Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008) - [j15]Nadia Creignou, Miki Hermann, Andrei A. Krokhin
Complexity of Clausal Constraints Over Chains. Theory Comput. Syst. 42(2): 239-255 (2008) - [j14]Andrei A. Krokhin
Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. SIAM J. Discret. Math. 22(1): 312-328 (2008) - [c17]Andrei A. Bulatov, Andrei A. Krokhin
Dualities for Constraint Satisfaction Problems. Complexity of Constraints 2008: 93-124 - [c16]Andrei A. Krokhin
On the Hardness of Losing Weight. ICALP (1) 2008: 662-673 - [c15]Catarina Carvalho
Caterpillar Duality for Constraint Satisfaction Problems. LICS 2008: 307-316 - 2007
- [j13]Peter Jonsson, Andrei A. Krokhin
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73(5): 691-702 (2007) - [j12]Víctor Dalmau, Andrei A. Krokhin, Benoît Larose:
First-order Definable Retraction Problems for Posets and Reflexive Graphs. J. Log. Comput. 17(1): 31-51 (2007) - [c14]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193 - [i5]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen:
Hard constraint satisfaction problems have hard gaps at location 1. CoRR abs/0712.1532 (2007) - 2006
- [j11]David A. Cohen, Martin C. Cooper
The complexity of soft constraint satisfaction. Artif. Intell. 170(11): 983-1016 (2006) - [j9]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35(6): 1329-1349 (2006) - [i4]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The approximability of MAX CSP with fixed-value constraints. CoRR abs/cs/0602075 (2006) - 2005
- [j8]David A. Cohen, Martin C. Cooper
Supermodular functions and the complexity of MAX CSP. Discret. Appl. Math. 149(1-3): 53-72 (2005) - [j7]Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. 34(3): 720-742 (2005) - [c13]Andrei A. Krokhin
Maximum Constraint Satisfaction on Diamonds. CP 2005: 388-402 - 2004
- [j6]Peter Jonsson, Andrei A. Krokhin
Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004) - [j5]David A. Cohen, Martin C. Cooper
A Maximal Tractable Class of Soft Constraints. J. Artif. Intell. Res. 22: 1-22 (2004) - [j4]Andrei A. Krokhin
Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discret. Math. 17(3): 453-477 (2004) - [j3]Peter Jonsson, Andrei A. Krokhin
Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004) - [c12]Víctor Dalmau, Andrei A. Krokhin, Benoît Larose:
First-Order Definable Retraction Problems for Posets and Reflexive Graph. LICS 2004: 232-241 - [c11]David A. Cohen, Martin C. Cooper
Identifying Efficiently Solvable Cases of Max CSP. STACS 2004: 152-163 - [i3]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin:
The approximability of three-valued MAX CSP. CoRR abs/cs/0412042 (2004) - 2003
- [j2]Andrei A. Krokhin
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50(5): 591-640 (2003) - [c10]David A. Cohen, Martin C. Cooper
Soft Constraints: Complexity and Multimorphisms. CP 2003: 244-258 - [c9]Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin:
Quantified Constraints: Algorithms and Complexity. CSL 2003: 58-70 - [c8]David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin:
A Maximal Tractable Class of Soft Constraints. IJCAI 2003: 209-214 - [c7]Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons:
Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL 2003: 343-354 - [c6]Andrei A. Krokhin, Benoît Larose:
Solving Order Constraints in Logarithmic Space. STACS 2003: 379-390 - [i2]Andrei A. Krokhin, Peter Jonsson:
Recognizing Frozen Variables in Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [c5]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454 - [c4]Andrei A. Krokhin
Extending the Point Algebra into the Qualitative Algebra. TIME 2002: 28-35 - 2001
- [c3]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. IJCAI 2001: 83-88 - [c2]Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
The complexity of maximal constraint languages. STOC 2001: 667-674 - [i1]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson:
The complexity of constraints on intervals and lengths. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [c1]Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons:
Constraint Satisfaction Problems and Finite Algebras. ICALP 2000: 272-282
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-11-16 00:38 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: