Outputs (5)

Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic (2017)
Journal Article
Glaßer, C., Jonsson, P., & Martin, B. (2017). Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science, 703, 18-36. https://doi.org/10.1016/j.tcs.2017.08.025

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [1] in the context of CSPs and settle the major open question from that pap... Read More about Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic.

The complexity of quantified constraints using the algebraic formulation (2017)
Presentation / Conference Contribution
Carvalho, C., Martin, B., Zhuk, D., Larsen, K. G., Bodlaender, H. L., & Raskin, J.-F. (2017, December). The complexity of quantified constraints using the algebraic formulation. Presented at Mathematical Foundation of Computer Science, Aalborg, Denmark

Let A be an idempotent algebra on a finite domain. We combine results of Chen, Zhuk and Carvalho et al. to argue that if A satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove... Read More about The complexity of quantified constraints using the algebraic formulation.

The packing chromatic number of the infinite square lattice is between 13 and 15 (2017)
Journal Article
Martin, B., Raimondi, F., Chen, T., & Martin, J. (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics, 225, 136-142. https://doi.org/10.1016/j.dam.2017.03.013

Using a SAT-solver on top of a partial previously-known solution we improve the upper bound of the packing chromatic number of the infinite square lattice from 17 to 15. We discuss the merits of SAT-solving for this kind of problem as well as compare... Read More about The packing chromatic number of the infinite square lattice is between 13 and 15.

Quantified Constraint Satisfaction Problem on semicomplete digraphs (2017)
Journal Article
Đapić, P., Marković, P., & Martin, B. (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic, 18(1), Article 2. https://doi.org/10.1145/3007899

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over semicomplete digraphs. We obtain a complexity-theoretic trichotomy: QCSP(H) is either in P, is NP-complete, or is Pspace-complete. The largest part of our... Read More about Quantified Constraint Satisfaction Problem on semicomplete digraphs.

The complexity of counting quantifiers on equality languages (2017)
Journal Article
Martin, B., Pongrácz, A., & Wrona, M. (2017). The complexity of counting quantifiers on equality languages. Theoretical Computer Science, 670, 56-67. https://doi.org/10.1016/j.tcs.2017.01.022

An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existe... Read More about The complexity of counting quantifiers on equality languages.