Publications

2025

1. A Fine-Grained Complexity View on Propositional Abduction – Algorithms and Lower Bounds

   Victor Lagerkvist, Mohamed Maizia, and Johannes Schmidt

   In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025

   Bib PDF

   @inproceedings{lagerkvist2025b,
     title = {A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds},
     author = {Lagerkvist, Victor and Maizia, Mohamed and Schmidt, Johannes},
     year = {2025},
     booktitle = {Proceedings of the 34th International Joint Conference on
                    Artificial Intelligence ({IJCAI}-2025)},
     publisher = {ijcai.org},
   }

2. Facets in Argumentation: A Formal Approach to Argument Significance

   Johannes Fichte, Nicolas Fröhlich, Markus Hecher , and 4 more authors

   In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025

   Bib PDF

   @inproceedings{lagerkvist2025a,
     title = {Facets in Argumentation: A Formal Approach to Argument Significance},
     author = {Fichte, Johannes and Fröhlich, Nicolas and Hecher, Markus and Lagerkvist, Victor and Mahmood, Yasir and Meier, Arne and Persson, Jonathan},
     year = {2025},
     booktitle = {Proceedings of the 34th International Joint Conference on
                    Artificial Intelligence ({IJCAI}-2025)},
     publisher = {ijcai.org},
   }

2024

1. Solving Quantified Boolean Formulas with Few Existential Variables

   L. Eriksson, V. Lagerkvist, G. Osipov , and 3 more authors

   In Proceedings of the 33 International Joint Conference on Artificial Intelligence (IJCAI-2024) , 2024

   Bib PDF

   @inproceedings{lagerkvist2024a,
     author = {Eriksson, L. and Lagerkvist, V. and Osipov, G. and Ordyniak, S. and Panolan, F. and Rychlicki, M.},
     title = {Solving Quantified {B}oolean Formulas with Few Existential Variables},
     booktitle = {Proceedings of the 33 International Joint Conference on
                    Artificial Intelligence ({IJCAI}-2024)},
     publisher = {ijcai.org},
     year = {2024},
   }

2. The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzazewski Conjecture

   B. Ambroise, M. Couceiro, and V. Lagerkvist

   Journal of Multiple-Valued Logic and Soft Computing, 2024

   Bib PDF

   @article{lagerkvist2024c,
     author = {Ambroise, B. and Couceiro, M. and Lagerkvist, V.},
     title = {The Fine-Grained Complexity of Graph Homomorphism Problems: Towards
                       the Okrasa and Rzazewski Conjecture},
     journal = {Journal of Multiple-Valued Logic and Soft Computing},
     publisher = {Old City Publishing},
     year = {2024},
   }

3. CSPs with Few Alien Constraints

   Peter Jonsson, V. Lagerkvist, and George Osipov

   In Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming (CP-2024) , 2024

   Bib PDF

   @inproceedings{lagerkvist2024b,
     author = {Jonsson, Peter and Lagerkvist, V. and Osipov, George},
     title = {CSPs with Few Alien Constraints},
     booktitle = {Proceedings of the 30th International Conference on Principles and Practice of Constraint
                       Programming ({CP}-2024)},
     series = {LIPIcs},
     volume = {307},
     pages = {15:1--15:17},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
     year = {2024},
     doi = {10.4230/LIPICS.CP.2024.15},
   }

2023

1. Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear Partitioning

   L. Eriksson, and V. Lagerkvist

   In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) , 2023

   Bib PDF

   @inproceedings{lagerkvist2023a,
     author = {Eriksson, L. and Lagerkvist, V.},
     title = {Improved Algorithms for {A}llen's Interval Algebra by Dynamic Programming with Sublinear Partitioning},
     booktitle = {Proceedings of the 32nd International Joint Conference on
                    Artificial Intelligence ({IJCAI}-2023)},
     publisher = {ijcai.org},
     year = {2023},
     pages = {1919--1926},
   }

2. A Fast Algorithm for Consistency Checking Partially Ordered Time

   L. Eriksson, and V. Lagerkvist

   In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) , 2023

   PDF
3. General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs

   P. Jonsson, and V. Lagerkvist

   Algorithmica, Aug 2023

   Bib PDF

   @article{Jonsson2022,
     author = {Jonsson, P. and Lagerkvist, V.},
     title = {General Lower Bounds and Improved Algorithms for Infinite-Domain {CSP}s},
     journal = {Algorithmica},
     year = {2023},
     month = aug,
     day = {11},
     issn = {1432-0541},
     doi = {10.1007/s00453-022-01017-8},
     url = {https://doi.org/10.1007/s00453-022-01017-8},
   }

2022

1. Computational Short Cuts in Infinite Domain Constraint Satisfaction

   P. Jonsson, V. Lagerkvist, and S. Ordyniak

   Journal of Artificial Intelligence Research, Aug 2022

   Bib PDF

   @article{lagerkvist2022e,
     author = {Jonsson, P. and Lagerkvist, V. and Ordyniak, S.},
     title = {Computational Short Cuts in Infinite Domain Constraint Satisfaction},
     journal = {Journal of Artificial Intelligence Research},
     year = {2022},
     doi = {https://doi.org/10.1613/jair.1.13787},
     volume = {75},
   }

2. The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems

   V. Lagerkvist, and M. Wahlström

   ACM Transactions on Computation Theory, Aug 2022

   Bib PDF

   @article{lagerkvist2022a,
     author = {Lagerkvist, V. and Wahlstr\"{o}m, M.},
     title = {The (Coarse) Fine-Grained Structure of {NP}-Hard {SAT} and {CSP} Problems},
     journal = {ACM Transactions on Computation Theory},
     year = {2022},
     issue_date = {March 2022},
     publisher = {Association for Computing Machinery},
     address = {New York, NY, USA},
     volume = {14},
     number = {1},
     issn = {1942-3454},
     url = {https://doi.org/10.1145/3492336},
     doi = {10.1145/3492336},
   }

3. A Multivariate Complexity Analysis of Qualitative Reasoning Problems

   L. Eriksson, and V. Lagerkvist

   In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-2022) , Aug 2022

   Bib PDF

   @inproceedings{lagerkvist2022d,
     author = {Eriksson, L. and Lagerkvist, V.},
     title = {A Multivariate Complexity Analysis of Qualitative Reasoning Problems},
     booktitle = {Proceedings of the 31st International Joint Conference on
                    Artificial Intelligence ({IJCAI}-2022)},
     pages = {1804--1810},
     publisher = {ijcai.org},
     year = {2022},
     url = {https://doi.org/10.24963/ijcai.2022/251},
     doi = {10.24963/ijcai.2022/251},
     timestamp = {Wed, 27 Jul 2022 16:43:00 +0200},
     biburl = {https://dblp.org/rec/conf/ijcai/ErikssonL22.bib},
     bibsource = {dblp computer science bibliography, https://dblp.org},
   }

4. An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems

   A. Baril, M. Couceiro, and V. Lagerkvist

   In Proceedings of the 52nd International Symposium on Multiple-Valued Logic (ISMVL-2022) , Aug 2022

   Bib PDF

   @inproceedings{lagerkvist2022c,
     title = {An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring Problems},
     author = {Baril, A. and Couceiro, M. and Lagerkvist, V.},
     booktitle = {Proceedings of the 52nd International Symposium on Multiple-Valued Logic ({ISMVL}-2022)},
     publisher = {{IEEE}},
     pages = {94--99},
     year = {2022},
     url = {https://doi.org/10.1109/ISMVL52857.2022.00021},
     doi = {10.1109/ISMVL52857.2022.00021},
     timestamp = {Wed, 29 Jun 2022 17:24:42 +0200},
     biburl = {https://dblp.org/rec/conf/ismvl/BarilCL22.bib},
     bibsource = {dblp computer science bibliography, https://dblp.org},
   }

5. A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial Polymorphisms

   M. Couceiro, L. Haddad, and V. Lagerkvist

   Journal of Multiple-Valued Logic and Soft Computing, Aug 2022

   Bib PDF

   @article{lagerkvist2022b,
     author = {Couceiro, M. and Haddad, L. and Lagerkvist, V.},
     title = {A Survey on the Fine-grained Complexity of Constraint
       Satisfaction Problems Based on Partial Polymorphisms},
     journal = {Journal of Multiple-Valued Logic and Soft Computing},
     volume = {38},
     number = {1-2},
     pages = {115--136},
     publisher = {Old City Publishing},
     year = {2022},
   }

6. C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases

   V. Lagerkvist, and B. Roy

   Journal of Multiple Valued Logic and Soft Computing, Aug 2022

   Bib PDF

   @article{lagerkvist2021h,
     author = {Lagerkvist, V. and Roy, B.},
     title = {C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean
                    Weak Bases},
     journal = {Journal of Multiple Valued Logic and Soft Computing},
     volume = {38},
     number = {3-4},
     pages = {333--353},
     year = {2022},
   }

2021

1. Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms

   P. Jonsson, V. Lagerkvist, and G. Osipov

   Artificial Intelligence, Aug 2021

   Bib PDF

   @article{lagerkvist2021a,
     author = {Jonsson, P. and Lagerkvist, V. and Osipov, G.},
     title = {Acyclic Orders, Partition Schemes and {CSP}s: Unified Hardness Proofs and Improved Algorithms},
     journal = {Artificial Intelligence},
     year = {2021},
     volume = {296},
     pages = {103505},
     issn = {0004-3702},
   }

2. Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem

   V. Lagerkvist, and B. Roy

   Journal of Computer and System Sciences, Aug 2021

   Bib PDF

   @article{lagerkvist2020e,
     title = {Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem},
     journal = {Journal of Computer and System Sciences},
     year = {2021},
     volume = {117},
     pages = {23-39},
     author = {Lagerkvist, V. and Roy, B.},
   }

3. The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

   P. Jonsson, V. Lagerkvist, J. Schmidt , and 1 more author

   Theoretical Computer Science, Aug 2021

   Bib PDF

   @article{lagerkvist2021g,
     title = {The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems},
     journal = {Theoretical Computer Science},
     volume = {892},
     pages = {1--24},
     year = {2021},
     issn = {0304-3975},
     author = {Jonsson, P. and Lagerkvist, V. and Schmidt, J. and Uppman, H.},
   }

4. Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors

   P. Jonsson, V. Lagerkvist, and S. Ordyniak

   In Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP-2021) , Aug 2021

   Bib PDF

   @inproceedings{lagerkvist2021f,
     author = {Jonsson, P. and Lagerkvist, V. and Ordyniak, S.},
     title = {Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors},
     booktitle = {Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming ({CP-2021})},
     year = {2021},
     series = {Lecture Notes in Computer Science},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
     volume = {210},
     pages = {32:1--32:20},
   }

5. Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming Approach

   L. Eriksson, and V. Lagerkvist

   In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2021) , Aug 2021

   Bib PDF

   @inproceedings{lagerkvist2021b,
     author = {Eriksson, L. and Lagerkvist, V.},
     title = {Improved Algorithms for {A}llen's Interval Algebra: a Dynamic Programming Approach},
     booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence ({IJCAI}-2021)},
     year = {2021},
     pages = {1873--1879},
     publisher = {ijcai.org},
   }

6. Fine-Grained Time Complexity of Constraint Satisfaction Problems

   P. Jonsson, V. Lagerkvist, and B. Roy

   ACM Transactions on Computation Theory, Aug 2021

   Bib PDF

   @article{lagerkvist2020f,
     author = {Jonsson, P. and Lagerkvist, V. and Roy, B.},
     title = {Fine-Grained Time Complexity of Constraint Satisfaction Problems},
     journal = {ACM Transactions on Computation Theory},
     publisher = {Association for Computing Machinery},
     year = {2021},
     volume = {13},
     number = {1},
     articleno = {2},
     numpages = {32},
   }

2020

1. A New Characterization of Restriction-Closed Hyperclones

   V. Lagerkvist

   In Proceedings of the 50th International Symposium on Multiple-Valued Logic (ISMVL-2020) , Aug 2020

   Bib PDF

   @inproceedings{lagerkvist2020a,
     author = {Lagerkvist, V.},
     title = {A New Characterization of Restriction-Closed Hyperclones},
     booktitle = {Proceedings of the 50th International Symposium on Multiple-Valued Logic ({ISMVL}-2020)},
     publisher = {{IEEE} Computer Society},
     year = {2020},
     pages = {303-308},
     doi = {10.1109/ISMVL49045.2020.00063},
   }

2. Sparsification of SAT and CSP Problems via Tractable Extensions

   V. Lagerkvist, and M. Wahlström

   ACM Transactions on Computation Theory, Aug 2020

   Bib PDF

   @article{lagerkvist2020b,
     author = {Lagerkvist, V. and Wahlstr\"om, M.},
     title = {Sparsification of {SAT} and {CSP} Problems via Tractable Extensions},
     journal = {ACM Transactions on Computation Theory},
     publisher = {Association for Computing Machinery},
     year = {2020},
     articleno = {13},
     numpages = {29},
     volume = {12},
     number = {2},
     address = {New York, NY, USA},
     issn = {1942-3454},
   }

3. Lower Bounds and Faster Algorithms for Equality Constraints

   P. Jonsson, and V. Lagerkvist

   In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-2020) , Aug 2020

   Bib PDF

   @inproceedings{lagerkvist2020c,
     author = {Jonsson, P. and Lagerkvist, V.},
     title = {Lower Bounds and Faster Algorithms for Equality Constraints},
     booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence ({IJCAI}-2020)},
     year = {2020},
     pages = {1784--1790},
   }

2019

1. On the Strength of Uniqueness Quantification in Primitive Positive Formulas

   V. Lagerkvist, and G. Nordh

   In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS-2019) , Aug 2019

   Bib PDF

   @inproceedings{lagerkvist2019,
     author = {Lagerkvist, V. and Nordh, G.},
     title = {On the Strength of Uniqueness Quantification in Primitive Positive Formulas},
     booktitle = {Proceedings of the 44th International Symposium on Mathematical Foundations of Computer
                    Science ({MFCS}-2019)},
     series = {LIPIcs},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
     volume = {138},
     pages = {36:1--36:15},
     year = {2019},
   }

2. The Inclusion Structure of Boolean Weak Bases

   V. Lagerkvist, and B. Roy

   In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) , Aug 2019

   Bib PDF

   @inproceedings{lagerkvist2019b,
     author = {Lagerkvist, V. and Roy, B.},
     title = {The Inclusion Structure of {B}oolean Weak Bases},
     booktitle = {Proceedings of the 49th International Symposium on Multiple-Valued Logic ({ISMVL}-2019)},
     publisher = {{IEEE} Computer Society},
     year = {2019},
     pages = {31--36},
   }

3. Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey

   M. Couceiro, L. Haddad, and V. Lagerkvist

   In Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) , Aug 2019

   Bib PDF

   @inproceedings{lagerkvist2019a,
     author = {Couceiro, M. and Haddad, L. and Lagerkvist, V.},
     title = {Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey},
     booktitle = {Proceedings of the 49th International Symposium on Multiple-Valued Logic ({ISMVL}-2019)},
     publisher = {{IEEE} Computer Society},
     year = {2019},
     pages = {170-175},
   }

2018

1. Why are CSPs Based on Partition Schemes Computationally Hard?

   P. Jonsson, and V. Lagerkvist

   In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018) , Aug 2018

   Bib PDF

   @inproceedings{DBLP:conf/mfcs/JonssonL18,
     author = {Jonsson, P. and Lagerkvist, V.},
     title = {Why are {CSP}s Based on Partition Schemes Computationally Hard?},
     booktitle = {Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer
                    Science ({MFCS}-2018)},
     series = {LIPIcs},
     volume = {117},
     pages = {43:1--43:15},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
     year = {2018},
   }

2017

1. The power of primitive positive definitions with polynomially many variables

   V. Lagerkvist, and M. Wahlström

   Journal of Logic and Computation, Aug 2017

   Bib PDF

   @article{lagerkvist2017c,
     author = {Lagerkvist, V. and Wahlstr\"om, M.},
     title = {The power of primitive positive definitions with polynomially many variables},
     journal = {Journal of Logic and Computation},
     volume = {27},
     number = {5},
     pages = {1465-1488},
     year = {2017},
     doi = {10.1093/logcom/exw005},
   }

2. On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total Operations

   M. Couceiro, L. Haddad, V. Lagerkvist , and 1 more author

   In Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL-2017) , Aug 2017

   Bib PDF

   @inproceedings{lagerkvist2017,
     author = {Couceiro, M. and Haddad, L. and Lagerkvist, V. and Roy, B.},
     title = {On the Interval of {B}oolean Strong Partial Clones Containing Only Projections
                    as Total Operations},
     booktitle = {Proceedings of the 47th International Symposium on Multiple-Valued Logic ({ISMVL}-2017)},
     pages = {88--93},
     publisher = {{IEEE} Computer Society},
     year = {2017},
   }

3. Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra

   V. Lagerkvist, and M. Wahlström

   In Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP-2017) , Aug 2017

   Bib PDF

   @inproceedings{lagerkvist2017b,
     author = {Lagerkvist, V. and Wahlstr{\"o}m, M.},
     title = {Kernelization of Constraint Satisfaction Problems: A Study Through Universal Algebra},
     booktitle = {Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming ({CP-2017})},
     year = {2017},
     publisher = {Springer International Publishing},
     pages = {157--171},
     isbn = {978-3-319-66158-2},
   }

4. Strong partial clones and the time complexity of SAT problems

   P. Jonsson, V. Lagerkvist, G. Nordh , and 1 more author

   Journal of Computer and System Sciences, Aug 2017

   Bib PDF

   @article{jonsson2017,
     title = {Strong partial clones and the time complexity of {SAT} problems },
     journal = {Journal of Computer and System Sciences},
     volume = {84},
     number = {},
     pages = {52 - 78},
     year = {2017},
     note = {},
     issn = {0022-0000},
     author = {Jonsson, P. and Lagerkvist, V. and Nordh, G. and Zanuttini, B.},
   }

5. A Dichotomy Theorem for the Inverse Satisfiability Problem

   V. Lagerkvist, and B. Roy

   In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2017) , Aug 2017

   Bib PDF

   @inproceedings{lagerkvist207f,
     author = {Lagerkvist, V. and Roy, B.},
     title = {A Dichotomy Theorem for the Inverse Satisfiability Problem},
     booktitle = {Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ({FSTTCS}-2017)},
     pages = {39:39--39:14},
     isbn = {978-3-95977-055-2},
     issn = {1868-8969},
     year = {2017},
     volume = {93},
   }

6. Time Complexity of Constraint Satisfaction via Universal Algebra

   P. Jonsson, V. Lagerkvist, and B. Roy

   In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017) , Aug 2017

   Bib PDF

   @inproceedings{lagerkvist2017e,
     author = {Jonsson, P. and Lagerkvist, V. and Roy, B.},
     year = {2017},
     pages = {17:1--17:15},
     isbn = {978-3-95977-046-0},
     issn = {1868-8969},
     title = {Time Complexity of Constraint Satisfaction via Universal Algebra},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
     booktitle = {Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science ({MFCS}-2017)},
   }

7. An initial study of time complexity in infinite-domain constraint satisfaction

   P. Jonsson, and V. Lagerkvist

   Artificial Intelligence, Aug 2017

   Bib PDF

   @article{lagerkvist2017d,
     author = {Jonsson, P. and Lagerkvist, V.},
     title = {An initial study of time complexity in infinite-domain constraint
                    satisfaction},
     journal = {Artificial Intelligence},
     volume = {245},
     pages = {115--133},
     year = {2017},
     doi = {10.1016/j.artint.2017.01.005},
     timestamp = {Sat, 27 May 2017 14:24:42 +0200},
     biburl = {http://dblp.uni-trier.de/rec/bib/journals/ai/JonssonL17},
     bibsource = {dblp computer science bibliography, http://dblp.org},
   }

2016

1. A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT

   V. Lagerkvist, and B. Roy

   In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016) , Aug 2016

   Bib PDF

   @inproceedings{Lagerkvist2016c,
     author = {Lagerkvist, V. and Roy, B.},
     title = {{A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT}},
     booktitle = {Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science ({MFCS}-2016)},
     pages = {64:1--64:14},
     year = {2016},
     volume = {58},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
   }

2015

1. Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPs

   P. Jonsson, and V. Lagerkvist

   In Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) , Aug 2015

   Bib PDF

   @inproceedings{lagerkvist2015c,
     year = {2015},
     isbn = {978-3-319-23218-8},
     booktitle = {Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming ({CP}-2015)},
     volume = {9255},
     series = {Lecture Notes in Computer Science},
     doi = {10.1007/978-3-319-23219-5_14},
     title = {Upper and Lower Bounds on the Time Complexity of Infinite-Domain {CSP}s},
     publisher = {Springer International Publishing},
     author = {Jonsson, P. and Lagerkvist, V.},
     pages = {183-199},
     language = {English},
   }

2. Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties

   P. Jonsson, V. Lagerkvist, and G. Nordh

   Theoretical Computer Science, May 2015

   Bib PDF

   @article{jonsson2015,
     author = {Jonsson, P. and Lagerkvist, V. and Nordh, G.},
     title = {Constructing {NP}-intermediate Problems by Blowing Holes with Parameters of Various Properties},
     journal = {Theoretical Computer Science},
     issue_date = {May 2015},
     volume = {581},
     number = {C},
     month = may,
     year = {2015},
     issn = {0304-3975},
     pages = {67--82},
     numpages = {16},
     doi = {10.1016/j.tcs.2015.03.009},
     acmid = {2781227},
     publisher = {Elsevier Science Publishers Ltd.},
     address = {Essex, UK},
   }

3. Bounded Bases of Strong Partial Clones

   V. Lagerkvist, M. Wahlström, and B. Zanuttini

   In Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015) , Waterloo, Canada, May 2015

   Bib PDF

   @inproceedings{lagerkvist2015,
     author = {Lagerkvist, V. and Wahlstr{\"{o}}m, M. and Zanuttini, B.},
     title = {Bounded Bases of Strong Partial Clones},
     booktitle = {Proceedings of the 45th International Symposium on Multiple-Valued Logic ({ISMVL}-2015)},
     location = {Waterloo, Canada},
     year = {2015},
     pages = {189--194},
     publisher = {{IEEE} Computer Society},
   }

4. Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem

   V. Lagerkvist

   In Proceedings of the Mathematical Foundations of Computer Science 2015 (MFCS-2015) , May 2015

   Bib PDF

   @inproceedings{lagerkvist2015b,
     year = {2015},
     isbn = {978-3-662-48056-4},
     booktitle = {Proceedings of the Mathematical Foundations of Computer Science 2015 ({MFCS}-2015)},
     volume = {9234},
     series = {Lecture Notes in Computer Science},
     doi = {10.1007/978-3-662-48057-1_28},
     title = {Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction Problem},
     publisher = {Springer Berlin Heidelberg},
     author = {Lagerkvist, V.},
     pages = {357-368},
     language = {English},
   }

2014

1. Weak bases of Boolean co-clones

   V. Lagerkvist

   Information Processing Letters, May 2014

   Bib PDF

   @article{Lagerkvist2014,
     author = {Lagerkvist, V.},
     title = {Weak bases of {B}oolean co-clones},
     journal = {Information Processing Letters},
     volume = {114},
     number = {9},
     year = {2014},
     pages = {462-468},
   }

2. Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

   P. Jonsson, V. Lagerkvist, J. Schmidt , and 1 more author

   In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) , May 2014

   Bib PDF

   @inproceedings{jonssonetal2014,
     author = {Jonsson, P. and Lagerkvist, V. and Schmidt, J. and Uppman, H.},
     title = {Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis},
     year = {2014},
     pages = {408--419},
     booktitle = {Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)},
     publisher = {Springer-Verlag},
     address = {Berlin, Heidelberg},
   }

3. Polynomially Closed Co-Clones

   V. Lagerkvist, and M. Wahlström

   In Proceedings of the 44th International Symposium on Multiple-Valued Logic (ISMVL-2014) , May 2014

   Bib PDF

   @inproceedings{lagerkvistwahlstrom2014,
     author = {Lagerkvist, V. and Wahlstr\"om, M.},
     booktitle = {Proceedings of the 44th International Symposium on Multiple-Valued Logic ({ISMVL}-2014)},
     title = {Polynomially Closed Co-Clones},
     year = {2014},
     pages = {85 - 90},
     publisher = {{IEEE} Computer Society},
   }

2013

1. Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction

   P. Jonsson, V. Lagerkvist, and G. Nordh

   In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013) , May 2013

   Bib PDF

   @inproceedings{lagerkvist2013b,
     year = {2013},
     isbn = {978-3-642-40626-3},
     booktitle = {Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming ({CP}-2013)},
     volume = {8124},
     series = {Lecture Notes in Computer Science},
     doi = {10.1007/978-3-642-40627-0_32},
     title = {Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction},
     publisher = {Springer Berlin Heidelberg},
     author = {Jonsson, P. and Lagerkvist, V. and Nordh, G.},
     pages = {398-414},
     language = {English},
   }

2. Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis

   P. Jonsson, V. Lagerkvist, G. Nordh , and 1 more author

   In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013) , May 2013

   Bib PDF

   @inproceedings{Jonsson:etal:soda2013,
     author = {Jonsson, P. and Lagerkvist, V. and Nordh, G. and Zanuttini, B.},
     title = {Complexity of {SAT} Problems, Clone Theory and the Exponential
                    Time Hypothesis},
     booktitle = {Proceedings of the 24th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA}-2013)},
     year = {2013},
     pages = {1264-1277},
     ee = {http://knowledgecenter.siam.org/0236-000094/},
     bibsource = {DBLP, http://dblp.uni-trier.de},
     publisher = {{SIAM}},
   }