Victor Lagerkvist

CoRR, 2024

Solving Quantified Boolean Formulas with Few Existential Variables.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

CSPs with Few Alien Constraints.

[BibT_eX]

[DOI]

George Osipov

Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming, 2024

2023

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

[BibT_eX]

[DOI]

Algorithmica, 2023

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

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

A Fast Algorithm for Consistency Checking Partially Ordered Time.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

2022

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2022

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

[BibT_eX]

[DOI]

J. Multiple Valued Log. Soft Comput., 2022

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

[BibT_eX]

[DOI]

Lucien Haddad

J. Multiple Valued Log. Soft Comput., 2022

Computational Short Cuts in Infinite Domain Constraint Satisfaction.

[BibT_eX]

[DOI]

Sebastian Ordyniak

J. Artif. Intell. Res., 2022

Component twin-width as a parameter for BINARY-CSP and its semiring generalisations.

[BibT_eX]

[DOI]

Ambroise Baril

CoRR, 2022

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

[BibT_eX]

[DOI]

Ambroise Baril

Proceedings of the 52nd IEEE International Symposium on Multiple-Valued Logic, 2022

A Multivariate Complexity Analysis of Qualitative Reasoning Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

2021

Fine-Grained Time Complexity of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2021

Acyclic orders, partition schemes and CSPs: Unified hardness proofs and improved algorithms.

[BibT_eX]

[DOI]

George Osipov

Artif. Intell., 2021

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

[BibT_eX]

[DOI]

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021

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

[BibT_eX]

[DOI]

Sebastian Ordyniak

Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, 2021

2020

Sparsification of SAT and CSP Problems via Tractable Extensions.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2020

A New Characterization of Restriction-Closed Hyperclones.

[BibT_eX]

[DOI]

Proceedings of the 50th IEEE International Symposium on Multiple-Valued Logic, 2020

Lower Bounds and Faster Algorithms for Equality Constraints.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

2019

On the Strength of Uniqueness Quantification in Primitive Positive Formulas.

[BibT_eX]

[DOI]

Gustav Nordh

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

The Inclusion Structure of Boolean Weak Bases.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Lucien Haddad

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

2018

Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?

[BibT_eX]

[DOI]

CoRR, 2018

Why are CSPs Based on Partition Schemes Computationally Hard?.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

The power of primitive positive definitions with polynomially many variables.

[BibT_eX]

[DOI]

J. Log. Comput., 2017

Strong partial clones and the time complexity of SAT problems.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

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

[BibT_eX]

[DOI]

Artif. Intell., 2017

Time Complexity of Constraint Satisfaction via Universal Algebra.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

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

[BibT_eX]

[DOI]

Proceedings of the 47th IEEE International Symposium on Multiple-Valued Logic, 2017

A Dichotomy Theorem for the Inverse Satisfiability Problem.

[BibT_eX]

[DOI]

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

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

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2017

2016

Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications.

[BibT_eX]

[DOI]

PhD thesis, 2016

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

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Constructing NP-intermediate problems by blowing holes with parameters of various properties.

[BibT_eX]

[DOI]

Gustav Nordh

Theor. Comput. Sci., 2015

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Bounded Bases of Strong Partial Clones.

[BibT_eX]

[DOI]

Bruno Zanuttini

Proceedings of the 2015 IEEE International Symposium on Multiple-Valued Logic, 2015

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

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2015

2014

Weak bases of Boolean co-clones.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

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

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Polynomially Closed Co-clones.

[BibT_eX]

[DOI]

Proceedings of the IEEE 44th International Symposium on Multiple-Valued Logic, 2014

2013

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

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

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

[BibT_eX]

[DOI]