Andrei A. Krokhin

99 papers A* 14A 6B 2C 1Misc 1Journal 66Unranked 5

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	1-in-3 vs. Not-All-Equal: Dichotomy of a Broken Promise. ACM Trans. Comput. Log. Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2024	A*	`conf`	1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. LICS Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2024	J	`jnl`	Functors on Relational Structures Which Admit Both Left and Right Adjoints. SIAM J. Discret. Math. Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
2024	J	`jnl`	Manuel Bodirsky. Bull. Symb. Log. Andrei A. Krokhin
2023	J	`jnl`	Functors on relational structures which admit both left and right adjoints. CoRR Víctor Dalmau, Andrei A. Krokhin, Jakub Oprsal
2023	J	`jnl`	On the complexity of the approximate hypergraph homomorphism problem. CoRR Lorenzo Ciardo, Marcin Kozik, Andrei A. Krokhin, Tamio-Vesa Nakajima, Stanislav Zivný
2023	J	`jnl`	Topology and Adjunction in Promise Constraint Satisfaction. SIAM J. Comput. Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2022	J	`jnl`	An Invitation to the Promise Constraint Satisfaction Problem. Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Jakub Oprsal
2022	J	`jnl`	An invitation to the promise constraint satisfaction problem. CoRR Andrei A. Krokhin, Jakub Oprsal
2022	J	`jnl`	An invitation to the promise constraint satisfaction problem. ACM SIGLOG News Andrei A. Krokhin, Jakub Oprsal
2021	J	`jnl`	Algebraic Approach to Promise Constraint Satisfaction. J. ACM Libor Barto, Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2020	J	`jnl`	Topology and adjunction in promise constraint satisfaction. CoRR Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	Topology and adjunction in promise constraint satisfaction. Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný
2019	A*	`conf`	Algebraic approach to promise constraint satisfaction. STOC Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2019	J	`jnl`	Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs. SIAM J. Comput. Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2019	A*	`conf`	The Complexity of 3-Colouring H-Colourable Graphs. FOCS Andrei A. Krokhin, Jakub Oprsal
2019	J	`jnl`	The complexity of 3-colouring Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Jakub Oprsal
2019	J	`jnl`	The complexity of 3-colouring H-colourable graphs. CoRR Andrei A. Krokhin, Jakub Oprsal
2018	J	`jnl`	Algebraic approach to promise constraint satisfaction. CoRR Jakub Bulín, Andrei A. Krokhin, Jakub Oprsal
2018	J	`jnl`	Towards a characterization of constant-factor approximable finite-valued CSPs. J. Comput. Syst. Sci. Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
2017	J	`jnl`	Binarisation for Valued Constraint Satisfaction Problems. SIAM J. Discret. Math. David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný
2017	J	`jnl`	On the hardness of losing weight. CoRR Andrei A. Krokhin, Dániel Marx
2017	—	`ch.`	Polymorphisms, and How to Use Them. The Constraint Satisfaction Problem Libor Barto, Andrei A. Krokhin, Ross Willard
2017	A*	`conf`	Robust algorithms with polynomial loss for near-unanimity CSPs. SODA Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2017	J	`jnl`	The Complexity of General-Valued CSPs. SIAM J. Comput. Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2017	—	`ch.`	The Complexity of Valued CSPs. The Constraint Satisfaction Problem Andrei A. Krokhin, Stanislav Zivný
2017	—	`book`	The Constraint Satisfaction Problem: Complexity and Approximability The Constraint Satisfaction Problem Andrei A. Krokhin, Stanislav Zivný
2016	J	`jnl`	Binarisation for Valued Constraint Satisfaction Problems. CoRR David A. Cohen, Martin C. Cooper, Peter G. Jeavons, Andrei A. Krokhin, Robert Powell, Stanislav Zivný
2016	J	`jnl`	On algebras with many symmetric operations. Int. J. Algebra Comput. Catarina Carvalho, Andrei A. Krokhin
2016	J	`jnl`	Robust algorithms with polynomial loss for near-unanimity CSPs. CoRR Víctor Dalmau, Marcin Kozik, Andrei A. Krokhin, Konstantin Makarychev, Yury Makarychev, Jakub Oprsal
2016	J	`jnl`	Towards a Characterization of Constant-Factor Approximable Finite-Valued CSPs. CoRR Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
2015	J	`jnl`	A Reduction from Valued CSP to Min Cost Homomorphism Problem for Digraphs. CoRR Robert Powell, Andrei A. Krokhin
2015	A*	`conf`	The Complexity of General-Valued CSPs. FOCS Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2015	J	`jnl`	The Complexity of General-Valued CSPs. CoRR Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek
2015	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx
2015	A*	`conf`	Towards a Characterization of Constant-Factor Approximable Min CSPs. SODA Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran
2014	J	`jnl`	Oracle Tractability of Skew Bisubmodular Functions. SIAM J. Discret. Math. Anna Huber, Andrei A. Krokhin
2014	J	`jnl`	Skew Bisubmodularity and Valued CSPs. SIAM J. Comput. Anna Huber, Andrei A. Krokhin, Robert Powell
2014	J	`jnl`	The Complexity of Valued Constraint Satisfaction. Bull. EATCS Peter Jeavons, Andrei A. Krokhin, Stanislav Zivný
2013	J	`jnl`	Oracle Tractability of Skew Bisubmodular Functions. CoRR Anna Huber, Andrei A. Krokhin
2013	J	`jnl`	Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Trans. Comput. Theory Víctor Dalmau, Andrei A. Krokhin
2013	A*	`conf`	Skew Bisubmodularity and Valued CSPs. SODA Anna Huber, Andrei A. Krokhin, Robert Powell
2012	J	`jnl`	On the hardness of losing weight. ACM Trans. Algorithms Andrei A. Krokhin, Dániel Marx
2012	J	`jnl`	The Complexity of the List Homomorphism Problem for Graphs. Theory Comput. Syst. László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
2012	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451). Dagstuhl Reports Johan Håstad, Andrei A. Krokhin, Dániel Marx
2011	J	`jnl`	A Maximal Tractable Class of Soft Constraints CoRR David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2011	A*	`conf`	The Complexity of Evaluating First-Order Sentences over a Fixed Structure. LICS Andrei A. Krokhin
2011	J	`jnl`	Two new homomorphism dualities and lattice operations. J. Log. Comput. Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
2010	J	`jnl`	CSP duality and trees of bounded pathwidth. Theor. Comput. Sci. Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
2010	J	`jnl`	Retractions to Pseudoforests. SIAM J. Discret. Math. Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh
2010	A	`conf`	The Complexity of the List Homomorphism Problem for Graphs. STACS László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
2010	B	`conf`	Tree Dualities for Constraint Satisfaction. CSL Andrei A. Krokhin
2009	—	`conf`	09441 Abstracts Collection - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	—	`conf`	09441 Executive Summary - The Constraint Satisfaction Problem: Complexity and Approximability. The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	J	`jnl`	Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
2009	—	`ed.`	The Constraint Satisfaction Problem: Complexity and Approximability, 25.10. - 30.10.2009 The Constraint Satisfaction Problem: Complexity and Approximability Andrei A. Bulatov, Martin Grohe, Phokion G. Kolaitis, Andrei A. Krokhin
2009	J	`jnl`	The complexity of constraint satisfaction games and QCSP. Inf. Comput. Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, Andrei A. Krokhin
2009	J	`jnl`	The complexity of the list homomorphism problem for graphs CoRR László Egri, Andrei A. Krokhin, Benoît Larose, Pascal Tesson
2008	A*	`conf`	Caterpillar Duality for Constraint Satisfaction Problems. LICS Catarina Carvalho, Víctor Dalmau, Andrei A. Krokhin
2008	J	`jnl`	Complexity of Clausal Constraints Over Chains. Theory Comput. Syst. Nadia Creignou, Miki Hermann, Andrei A. Krokhin, Gernot Salzer
2008	J	`jnl`	Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. Peter Jonsson, Andrei A. Krokhin
2008	—	`conf`	Dualities for Constraint Satisfaction Problems. Complexity of Constraints Andrei A. Bulatov, Andrei A. Krokhin, Benoît Larose
2008	J	`jnl`	Majority constraints have bounded pathwidth duality. Eur. J. Comb. Víctor Dalmau, Andrei A. Krokhin
2008	J	`jnl`	Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction. SIAM J. Discret. Math. Andrei A. Krokhin, Benoît Larose
2008	—	`conf`	On the Hardness of Losing Weight. ICALP (1) Andrei A. Krokhin, Dániel Marx
2008	J	`jnl`	Retractions onto series-parallel posets. Discret. Math. Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
2008	J	`jnl`	The approximability of MAX CSP with fixed-value constraints. J. ACM Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
2007	J	`jnl`	First-order Definable Retraction Problems for Posets and Reflexive Graphs. J. Log. Comput. Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
2007	J	`jnl`	Hard constraint satisfaction problems have hard gaps at location 1 CoRR Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
2007	J	`jnl`	Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. Peter Jonsson, Andrei A. Krokhin
2007	Misc	`conf`	Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen
2006	J	`jnl`	A Monoidal Interval of Clones of Selfdual Functions. J. Autom. Lang. Comb. Andrei A. Krokhin, Ivo G. Rosenberg
2006	J	`jnl`	The Approximability of Three-valued MAX CSP. SIAM J. Comput. Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
2006	J	`jnl`	The approximability of MAX CSP with fixed-value constraints CoRR Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
2006	J	`jnl`	The complexity of soft constraint satisfaction. Artif. Intell. David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2005	J	`jnl`	Classifying the Complexity of Constraints Using Finite Algebras. SIAM J. Comput. Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
2005	A	`conf`	Maximum Constraint Satisfaction on Diamonds. CP Andrei A. Krokhin, Benoît Larose
2005	J	`jnl`	Supermodular functions and the complexity of MAX CSP. Discret. Appl. Math. David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2004	J	`jnl`	A Maximal Tractable Class of Soft Constraints. J. Artif. Intell. Res. David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2004	J	`jnl`	Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. Peter Jonsson, Andrei A. Krokhin
2004	J	`jnl`	Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discret. Math. Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
2004	A*	`conf`	First-Order Definable Retraction Problems for Posets and Reflexive Graph. LICS Víctor Dalmau, Andrei A. Krokhin, Benoît Larose
2004	A	`conf`	Identifying Efficiently Solvable Cases of Max CSP. STACS David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2004	J	`jnl`	Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. Peter Jonsson, Andrei A. Krokhin
2004	J	`jnl`	The approximability of three-valued MAX CSP CoRR Peter Jonsson, Mikael Klasson, Andrei A. Krokhin
2003	A*	`conf`	A Maximal Tractable Class of Soft Constraints. IJCAI David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2003	—	`conf`	Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. ISMVL Andrei A. Krokhin, Andrei A. Bulatov, Peter Jeavons
2003	B	`conf`	Quantified Constraints: Algorithms and Complexity. CSL Ferdinand Börner, Andrei A. Bulatov, Peter Jeavons, Andrei A. Krokhin
2003	J	`jnl`	Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
2003	J	`jnl`	Recognizing Frozen Variables in Constraint Satisfaction Problems Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Peter Jonsson
2003	A	`conf`	Soft Constraints: Complexity and Multimorphisms. CP David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin
2003	A	`conf`	Solving Order Constraints in Logarithmic Space. STACS Andrei A. Krokhin, Benoît Larose
2002	C	`conf`	Extending the Point Algebra into the Qualitative Algebra. TIME Andrei A. Krokhin, Peter Jonsson
2002	A	`conf`	The Complexity of Constraints on Intervals and Lengths. STACS Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
2001	A*	`conf`	A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. IJCAI Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
2001	J	`jnl`	Congruences of Clone Lattices, II. Order Andrei A. Krokhin
2001	J	`jnl`	The complexity of constraints on intervals and lengths Electron. Colloquium Comput. Complex. Andrei A. Krokhin, Peter Jeavons, Peter Jonsson
2001	A*	`conf`	The complexity of maximal constraint languages. STOC Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons
2000	A*	`conf`	Constraint Satisfaction Problems and Finite Algebras. ICALP Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons