Follow
Victor Lagerkvist
Title
Cited by
Cited by
Year
Strong partial clones and the time complexity of SAT problems
P Jonsson, V Lagerkvist, G Nordh, B Zanuttini
Journal of Computer and System Sciences 84, 52-78, 2017
362017
Complexity of SAT problems, clone theory and the exponential time hypothesis
P Jonsson, V Lagerkvist, G Nordh, B Zanuttini
Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete …, 2013
302013
Weak bases of Boolean co-clones
V Lagerkvist
Information Processing Letters 114 (9), 462-468, 2014
252014
An initial study of time complexity in infinite-domain constraint satisfaction
P Jonsson, V Lagerkvist
Artificial Intelligence 245, 115-133, 2017
222017
The power of primitive positive definitions with polynomially many variables
V Lagerkvist, M Wahlström
Journal of Logic and Computation 27 (5), 1465-1488, 2017
132017
Kernelization of constraint satisfaction problems: A study through universal algebra
V Lagerkvist, M Wahlström
International Conference on Principles and Practice of Constraint …, 2017
112017
Why are CSPs based on partition schemes computationally hard?
P Jonsson, V Lagerkvist
43rd International Symposium on Mathematical Foundations of Computer Science …, 2018
102018
Bounded bases of strong partial clones
V Lagerkvist, M Wahlström, B Zanuttini
2015 IEEE International Symposium on Multiple-Valued Logic, 189-194, 2015
102015
Time complexity of constraint satisfaction via universal algebra
P Jonsson, V Lagerkvist, B Roy
arXiv preprint arXiv:1706.05902, 2017
82017
Sparsification of SAT and CSP problems via tractable extensions
V Lagerkvist, M Wahlström
ACM Transactions on Computation Theory (TOCT) 12 (2), 1-29, 2020
72020
Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: A survey
M Couceiro, L Haddad, V Lagerkvist
2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), 170-175, 2019
72019
A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
V Lagerkvist, B Roy
41st International Symposium on Mathematical Foundations of Computer Science …, 2016
72016
Fine-grained time complexity of constraint satisfaction problems
P Jonsson, V Lagerkvist, B Roy
ACM Transactions on Computation Theory (TOCT) 13 (1), 1-32, 2021
62021
Which NP-hard SAT and CSP problems admit exponentially improved algorithms?
V Lagerkvist, M Wahlström
arXiv preprint arXiv:1801.09488, 2018
62018
A dichotomy theorem for the inverse satisfiability problem
V Lagerkvist, B Roy
37th IARCS Annual Conference on Foundations of Software Technology and …, 2018
62018
Strong Partial Clones and the Complexity of Constraint Satisfaction Problems: Limitations and Applications
V Lagerkvist
Linköping University Electronic Press, 2016
62016
Constructing np-intermediate problems by blowing holes with parameters of various properties
P Jonsson, V Lagerkvist, G Nordh
Theoretical Computer Science 581, 67-82, 2015
62015
Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms
P Jonsson, V Lagerkvist, G Osipov
Artificial Intelligence 296, 103505, 2021
52021
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
V Lagerkvist, B Roy
Journal of Computer and System Sciences 117, 23-39, 2021
52021
On the interval of Boolean strong partial clones containing only projections as total operations
M Couceiro, L Haddad, V Lagerqvist, B Roy
2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), 88-93, 2017
52017
The system can't perform the operation now. Try again later.
Articles 1–20