Outputs (2)

From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP (2015)
Conference Proceeding
Carvalho, C., Madelaine, F. R., & Martin, B. (2015). From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP. In Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015) : 6-10 July 2015, Kyoto, Japan (462-474). https://doi.org/10.1109/lics.2015.50

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Buildin... Read More about From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP.

Constraint Satisfaction Problems over the Integers with Successor (2015)
Conference Proceeding
Bodirsky, M., Martin, B., & Mottet, A. (2015). Constraint Satisfaction Problems over the Integers with Successor. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Proceedings. Part I (256-267). https://doi.org/10.1007/978-3-662-47672-7_21

A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z;succ)(Z;succ), i.e., over the integers with the successor function. Our main... Read More about Constraint Satisfaction Problems over the Integers with Successor.