@inproceedings{lagerkvist2026e,author={Brakensiek, J. and Guruswami, V. and Jansen, B. M. P. and Lagerkvist, V. and Wahlstr{\"{o}}m, M.},title={The Richness of {CSP} Non-redundancy},booktitle={Proceedings of the 67th Annual IEEE Symposium on Foundations of Computer Science ({FOCS}-2026)},year={2026},note={To appear},}
Maximum Satisfiability of Simple Temporal Problems
J. Fichte, J. Groven, V. Lagerkvist , and 2 more authors
In Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI-2026) , 2026
@inproceedings{lagerkvist2026g,title={Maximum Satisfiability of Simple Temporal Problems},author={Fichte, J. and Groven, J. and Lagerkvist, V. and Jonsson, P. and de Vlas, J. M.},year={2026},booktitle={Proceedings of the 35th International Joint Conference on Artificial Intelligence ({IJCAI}-2026)},publisher={ijcai.org},note={To appear},}
Representative Sets in Propositional Abduction
J. Schmidt, M. Maizia, V. Lagerkvist , and 1 more author
In Proceedings of the 42nd International Conference on Logic Programming (Technical Communications, ICLP-2026) , 2026
@inproceedings{lagerkvist2026f,author={Schmidt, J. and Maizia, M. and Lagerkvist, V. and Fichte, J.},title={Representative Sets in Propositional Abduction},booktitle={Proceedings of the 42nd International Conference on Logic Programming (Technical Communications, {ICLP}-2026)},year={2026},}
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
J. Brakensiek, V. Guruswami, B. M. P. Jansen , and 2 more authors
In Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC-2026) , 2026
@inproceedings{lagerkvist2026h,author={Brakensiek, J. and Guruswami, V. and Jansen, B. M. P. and Lagerkvist, V. and Wahlstr{\"{o}}m, M.},title={Super-linear Lower Bounds for {CSP} Non-Redundancy via Shrinking Instances},booktitle={Proceedings of the 21st International Symposium on Parameterized and Exact Computation ({IPEC}-2026)},year={2026},note={(Best paper award)},}
Clausal Deletion Backdoors for QBF: a Parameterized Complexity Approach
L. Eriksson, V. Lagerkvist, S. Ordyniak , and 3 more authors
In Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning (KR-2026) , 2026
@inproceedings{eriksson2026d,author={Eriksson, L. and Lagerkvist, V. and Ordyniak, S. and Osipov, G. and Panolan, F. and Rychlicki, M.},title={Clausal Deletion Backdoors for {QBF}: a Parameterized Complexity Approach},doi={10.24963/kr.2026/28},booktitle={Proceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning ({KR}-2026)},articleno={28},numpages={11},year={2026},}
Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
P. Jonsson, V. Lagerkvist, J. M. Vlas , and 1 more author
In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP-2026) , 2026
@inproceedings{lagerkvist2026c,author={Jonsson, P. and Lagerkvist, V. and de Vlas, J. M. and Wahlstr{\"{o}}m, M.},title={Going Beyond Twin-width? {CSP}s with Unbounded Domain and Few Variables},booktitle={Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming ({ICALP}-2026)},year={2026},doi={10.4230/LIPIcs.ICALP.2026.120},}
Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
L. Eriksson, J. Groven, and V. Lagerkvist
In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI-2026) , 2026
@inproceedings{lagerkvist2026b,author={Eriksson, L. and Groven, J. and Lagerkvist, V.},title={Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming},booktitle={Proceedings of the 40th AAAI Conference on Artificial Intelligence ({AAAI}-2026)},publisher={{AAAI} Press},year={2026},pages={14287--14294},}
New perspectives on semiring applications to dynamic programming
@article{lagerkvist2026a,title={New perspectives on semiring applications to dynamic programming},journal={Discrete Applied Mathematics},volume={383},pages={243-279},year={2026},issn={0166-218X},doi={https://doi.org/10.1016/j.dam.2025.12.035},url={https://www.sciencedirect.com/science/article/pii/S0166218X25007462},author={Baril, A. and Couceiro, M. and Lagerkvist, V.},keywords={Semiring, Dynamic programming, Fixed parameter tractability, Constraint satisfaction problems, Connected dominating set},}
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
@article{lagerkvist2025d,author={Baril, A. and Couceiro, M. and Lagerkvist, V.},title={Improved Bounds for Twin-Width Parameter Variants with Algorithmic
Applications to Counting Graph Colorings},journal={Theory of Computing Systems},year={2026},volume={70},issue={1},pages={12},doi={10.1007/s00224-025-10233-y},}
2025
Facets in Argumentation: A Formal Approach to Argument Significance
J. Fichte, N. Fröhlich, M. Hecher , and 4 more authors
In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025
@inproceedings{lagerkvist2025a,title={Facets in Argumentation: A Formal Approach to Argument Significance},author={Fichte, J. and Fr\"ohlich, N. and Hecher, M. and Lagerkvist, V. and Mahmood, Y. and Meier, A. and Persson, J.},year={2025},booktitle={Proceedings of the 34th International Joint Conference on
Artificial Intelligence ({IJCAI}-2025)},publisher={ijcai.org},}
Complexity of Faceted Explanations in Propositional Abduction
J. Schmidt, M. Maizia, V. Lagerkvist , and 1 more author
@article{lagerkvist2025c,title={Complexity of Faceted Explanations in Propositional Abduction},volume={25},doi={10.1017/S1471068425100215},number={4},journal={Theory and Practice of Logic Programming},author={Schmidt, J. and Maizia, M. and Lagerkvist, V. and Fichte, J.},year={2025},pages={775–793},}
A Fine-Grained Complexity View on Propositional Abduction – Algorithms and Lower Bounds
V. Lagerkvist, M. Maizia, and J. Schmidt
In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI-2025) , 2025
@inproceedings{lagerkvist2025b,title={A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds},author={Lagerkvist, V. and Maizia, M. and Schmidt, J.},year={2025},booktitle={Proceedings of the 34th International Joint Conference on
Artificial Intelligence ({IJCAI}-2025)},publisher={ijcai.org},}
2024
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
@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},}
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
@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},}
Solving Quantified Boolean Formulas with Few Existential Variables
L. Eriksson, V. Lagerkvist, G. Osipov , and 3 more authors
In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-2024) , 2024
@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 33rd International Joint Conference on
Artificial Intelligence ({IJCAI}-2024)},publisher={ijcai.org},year={2024},}
2023
General Lower Bounds and Improved Algorithms for Infinite-Domain CSPs
@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},}
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) , Aug 2023
@inproceedings{lagerkvist2023b,author={Eriksson, L. and Lagerkvist, V.},title={A Fast Algorithm for Consistency Checking Partially Ordered Time},booktitle={Proceedings of the 32nd International Joint Conference on
Artificial Intelligence ({IJCAI}-2023)},publisher={ijcai.org},year={2023},pages={1911--1918},}
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) , Aug 2023
@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},}
2022
The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
@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},}
Computational Short Cuts in Infinite Domain Constraint Satisfaction
P. Jonsson, V. Lagerkvist, and S. Ordyniak
Journal of Artificial Intelligence Research, Aug 2022
@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},}
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
@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},}
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
@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},}
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
@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},}
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
@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
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
@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},}
Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability Problem
@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.},}
Fine-Grained Time Complexity of Constraint Satisfaction Problems
@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},}
Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved Algorithms
@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},}
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
@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},}
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
P. Jonsson, V. Lagerkvist, J. Schmidt , and 1 more author
@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.},}
2020
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
@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},}
A New Characterization of Restriction-Closed Hyperclones
V. Lagerkvist
In Proceedings of the 50th International Symposium on Multiple-Valued Logic (ISMVL-2020) , Aug 2020
@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},}
Sparsification of SAT and CSP Problems via Tractable Extensions
@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},}
2019
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
@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},}
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
@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},}
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
@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},}
2018
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
@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
Strong partial clones and the time complexity of SAT problems
P. Jonsson, V. Lagerkvist, G. Nordh , and 1 more author
@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.},}
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
@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},}
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
@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)},}
An initial study of time complexity in infinite-domain constraint satisfaction
@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},}
The power of primitive positive definitions with polynomially many variables
@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},}
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
@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},}
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
@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},}
2016
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
@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
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
@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},}
Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties
@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},}
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
@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},}
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
@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},}
@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},}
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
@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
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
@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},}
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
@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}},}