Outputs (69)

Skew Bisubmodularity and Valued CSPs (2014)
Journal Article
Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084. https://doi.org/10.1137/120893549

An instance of the (finite-)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rational-valued) functions, with each function depending on a subset of the variables. The goal... Read More about Skew Bisubmodularity and Valued CSPs.

Robust Satisfiability for CSPs: Hardness and Algorithmic Results (2013)
Journal Article
Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs... Read More about Robust Satisfiability for CSPs: Hardness and Algorithmic Results.

On the hardness of losing weight. (2012)
Journal Article
Krokhin, A., & Marx, D. (2012). On the hardness of losing weight. ACM Transactions on Algorithms, 8(2), Article 19. https://doi.org/10.1145/2151171.2151182

Two new homomorphism dualities and lattice operations (2011)
Journal Article
Carvalho, C., Dalmau, V., & Krokhin, A. (2011). Two new homomorphism dualities and lattice operations. Journal of Logic and Computation, 21(6), 1065-1092. https://doi.org/10.1093/logcom/exq030

Retractions to pseudoforests. (2010)
Journal Article
Feder, T., Hell, P., Jonsson, P., Krokhin, A., & Nordh, G. (2010). Retractions to pseudoforests. SIAM Journal on Discrete Mathematics, 24(1), 101-112. https://doi.org/10.1137/080738866

The complexity of the list homomorphism problem for graphs. (2010)
Presentation / Conference Contribution
Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010, December). The complexity of the list homomorphism problem for graphs. Presented at Symposium on Theoretical Aspects of Computer Science., Nancy, France

On the hardness of losing weight (2010)
Journal Article
Krokhin, A., & Marx, D. (online). On the hardness of losing weight. https://doi.org/10.1007/978-3-540-70575-8_54

We study the complexity of local search for the Boolean constraint satisfaction problem (CSP), in the following form: given a CSP instance, that is, a collection of constraints, and a solution to it, the question is whether there is a better (lighter... Read More about On the hardness of losing weight.

CSP duality and trees of bounded pathwidth. (2010)
Journal Article
Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016

We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algeb... Read More about CSP duality and trees of bounded pathwidth..

Hard constraint satisfaction problems have hard gaps at location 1 (2009)
Journal Article
Jonsson, P., Krokhin, A., & Kuivinen, F. (2009). Hard constraint satisfaction problems have hard gaps at location 1. Theoretical Computer Science, 410(38-40), 3856-3874. https://doi.org/10.1016/j.tcs.2009.05.022

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures m... Read More about Hard constraint satisfaction problems have hard gaps at location 1.

The complexity of constraint satisfaction games and QCSP (2009)
Journal Article
Boerner, F., Bulatov, A., Chen, H., Jeavons, P., & Krokhin, A. (2009). The complexity of constraint satisfaction games and QCSP. Information and Computation, 207(9), 923-944. https://doi.org/10.1016/j.ic.2009.05.003

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain... Read More about The complexity of constraint satisfaction games and QCSP.