Publications

Journal articles and conference papers in reverse chronological order.

Journal Articles

2023

  1. General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs
    Jonsson, P., and Lagerkvist, V.
    Algorithmica 2023
    PDF

2022

  1. Computational Short Cuts in Infinite Domain Constraint Satisfaction
    Jonsson, P., Lagerkvist, V., and Ordyniak, S.
    Journal of Artificial Intelligence Research 2022
    PDF
  2. C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases
    Lagerkvist, V., and Roy, B.
    Journal of Multiple Valued Logic and Soft Computing 2022
    PDF
  3. Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
    Baril, A., Couceiro, M., and Lagerkvist, V.
    CoRR 2022
    PDF
  4. A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial Polymorphisms
    Couceiro, M., Haddad, L., and Lagerkvist, V.
    Journal of Multiple-Valued Logic and Soft Computing 2022
    PDF
  5. The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
    Lagerkvist, V., and Wahlström, M.
    ACM Transactions on Computation Theory 2022
    PDF

2021

  1. Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms
    Jonsson, P., Lagerkvist, V., and Osipov, G.
    Artificial Intelligence 2021
    PDF
  2. Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem
    Lagerkvist, V., and Roy, B.
    Journal of Computer and System Sciences 2021
    PDF
  3. Fine-Grained Time Complexity of Constraint Satisfaction Problems
    Jonsson, P., Lagerkvist, V., and Roy, B.
    ACM Transactions on Computation Theory 2021
    PDF
  4. The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
    Jonsson, P., Lagerkvist, V., Schmidt, J., and Uppman, H.
    Theoretical Computer Science 2021
    PDF

2020

  1. Sparsification of SAT and CSP Problems via Tractable Extensions
    Lagerkvist, V., and Wahlström, M.
    ACM Transactions on Computation Theory 2020
    PDF

2017

  1. An initial study of time complexity in infinite-domain constraint satisfaction
    Jonsson, P., and Lagerkvist, V.
    Artificial Intelligence 2017
    PDF
  2. The power of primitive positive definitions with polynomially many variables
    Lagerkvist, V., and Wahlström, M.
    Journal of Logic and Computation 2017
    PDF
  3. Strong partial clones and the time complexity of SAT problems
    Jonsson, P., Lagerkvist, V., Nordh, G., and Zanuttini, B.
    Journal of Computer and System Sciences 2017
    PDF

2015

  1. Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties
    Jonsson, P., Lagerkvist, V., and Nordh, G.
    Theoretical Computer Science 2015
    PDF

2014

  1. Weak bases of Boolean co-clones
    Lagerkvist, V.
    Information Processing Letters 2014
    PDF

Conferences Papers

2023

  1. A Fast Algorithm for Consistency Checking Partially Ordered Time
    Eriksson, L., and Lagerkvist, V.
    In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) 2023
    PDF
  2. Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning
    Eriksson, L., and Lagerkvist, V.
    In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) 2023
    PDF

2022

  1. A Multivariate Complexity Analysis of Qualitative Reasoning Problems
    Eriksson, L., and Lagerkvist, V.
    In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-2022) 2022
    PDF
  2. An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems
    Baril, A., Couceiro, M., and Lagerkvist, V.
    In Proceedings of the 52nd International Symposium on Multiple-Valued Logic (ISMVL-2022) 2022
    PDF

2021

  1. Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach
    Eriksson, L., and Lagerkvist, V.
    In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2021) 2021
    PDF
  2. Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors
    Jonsson, P., Lagerkvist, V., and Ordyniak, S.
    In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP-2021) 2021
    PDF

2020

  1. Lower Bounds and Faster Algorithms for Equality Constraints
    Jonsson, P., and Lagerkvist, V.
    In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-2020) 2020
    PDF
  2. A New Characterization of Restriction-Closed Hyperclones
    Lagerkvist, V.
    In Proceedings of the 50th International Symposium on Multiple-Valued Logic (ISMVL-2020) 2020
    PDF

2019

  1. Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey
    Couceiro, M., Haddad, L., and Lagerkvist, V.
    In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) 2019
    PDF
  2. The Inclusion Structure of Boolean Weak Bases
    Lagerkvist, V., and Roy, B.
    In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) 2019
    PDF
  3. On the Strength of Uniqueness Quantification in Primitive Positive Formulas
    Lagerkvist, V., and Nordh, G.
    In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS-2019) 2019
    PDF

2018

  1. Why are CSPs Based on Partition Schemes Computationally Hard?
    Jonsson, P., and Lagerkvist, V.
    In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018) 2018
    PDF

2017

  1. A Dichotomy Theorem for the Inverse Satisfiability Problem
    Lagerkvist, V., and Roy, B.
    In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2017) 2017
    PDF
  2. Time Complexity of Constraint Satisfaction via Universal Algebra
    Jonsson, P., Lagerkvist, V., and Roy, B.
    In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017) 2017
    PDF
  3. On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations
    Couceiro, M., Haddad, L., Lagerkvist, V., and Roy, B.
    In Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL-2017) 2017
    PDF
  4. Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra
    Lagerkvist, V., and Wahlström, M.
    In Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP-2017) 2017
    PDF

2016

  1. A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT
    Lagerkvist, V., and Roy, B.
    In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016) 2016
    PDF

2015

  1. Bounded Bases of Strong Partial Clones
    Lagerkvist, V., Wahlström, M., and Zanuttini, B.
    In Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015) 2015
    PDF
  2. Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs
    Jonsson, P., and Lagerkvist, V.
    In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) 2015
    PDF
  3. Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem
    Lagerkvist, V.
    In Proceedings of the Mathematical Foundations of Computer Science 2015 (MFCS-2015) 2015
    PDF

2014

  1. Polynomially Closed Co-Clones
    Lagerkvist, V., and Wahlström, M.
    In Proceedings of the 44th International Symposium on Multiple-Valued Logic (ISMVL-2014) 2014
    PDF
  2. Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
    Jonsson, P., Lagerkvist, V., Schmidt, J., and Uppman, H.
    In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) 2014
    PDF

2013

  1. Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction
    Jonsson, P., Lagerkvist, V., and Nordh, G.
    In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013) 2013
    PDF
  2. Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
    Jonsson, P., Lagerkvist, V., Nordh, G., and Zanuttini, B.
    In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013) 2013
    PDF