Publications
Journal articles and conference papers in reverse chronological order.
Journal Articles
2023
2022
- Computational Short Cuts in Infinite Domain Constraint SatisfactionJournal of Artificial Intelligence Research 2022
- C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak BasesJournal of Multiple Valued Logic and Soft Computing 2022
- A Survey on the Fine-grained Complexity of Constraint Satisfaction Problems Based on Partial PolymorphismsJournal of Multiple-Valued Logic and Soft Computing 2022
- The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP ProblemsACM Transactions on Computation Theory 2022
2021
- Acyclic Orders, Partition Schemes and CSPs: Unified Hardness Proofs and Improved AlgorithmsArtificial Intelligence 2021
- Complexity of Inverse Constraint Problems and a Dichotomy for the Inverse Satisfiability ProblemJournal of Computer and System Sciences 2021
- Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory 2021
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problemsTheoretical Computer Science 2021
2020
- Sparsification of SAT and CSP Problems via Tractable ExtensionsACM Transactions on Computation Theory 2020
2017
- An initial study of time complexity in infinite-domain constraint satisfactionArtificial Intelligence 2017
- The power of primitive positive definitions with polynomially many variablesJournal of Logic and Computation 2017
- Strong partial clones and the time complexity of SAT problemsJournal of Computer and System Sciences 2017
2015
- Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various PropertiesTheoretical Computer Science 2015
2014
Conferences Papers
2023
- A Fast Algorithm for Consistency Checking Partially Ordered TimeIn Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) 2023
- Improved Algorithms for Allen’s Interval Algebra by Dynamic Programming with Sublinear PartitioningIn Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI-2023) 2023
2022
- A Multivariate Complexity Analysis of Qualitative Reasoning ProblemsIn Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI-2022) 2022
- An Algebraic Approach Towards the Fine-Grained Complexity of Graph Coloring ProblemsIn Proceedings of the 52nd International Symposium on Multiple-Valued Logic (ISMVL-2022) 2022
2021
- Improved Algorithms for Allen’s Interval Algebra: a Dynamic Programming ApproachIn Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-2021) 2021
- Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for BackdoorsIn Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP-2021) 2021
2020
- Lower Bounds and Faster Algorithms for Equality ConstraintsIn Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI-2020) 2020
- A New Characterization of Restriction-Closed HyperclonesIn Proceedings of the 50th International Symposium on Multiple-Valued Logic (ISMVL-2020) 2020
2019
- Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A SurveyIn Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) 2019
- The Inclusion Structure of Boolean Weak BasesIn Proceedings of the 49th International Symposium on Multiple-Valued Logic (ISMVL-2019) 2019
- On the Strength of Uniqueness Quantification in Primitive Positive FormulasIn Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS-2019) 2019
2018
- Why are CSPs Based on Partition Schemes Computationally Hard?In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS-2018) 2018
2017
- A Dichotomy Theorem for the Inverse Satisfiability ProblemIn Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2017) 2017
- Time Complexity of Constraint Satisfaction via Universal AlgebraIn Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS-2017) 2017
- On the Interval of Boolean Strong Partial Clones Containing Only Projections as Total OperationsIn Proceedings of the 47th International Symposium on Multiple-Valued Logic (ISMVL-2017) 2017
- Kernelization of Constraint Satisfaction Problems: A Study Through Universal AlgebraIn Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP-2017) 2017
2016
- A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SATIn Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS-2016) 2016
2015
- Bounded Bases of Strong Partial ClonesIn Proceedings of the 45th International Symposium on Multiple-Valued Logic (ISMVL-2015) 2015
- Upper and Lower Bounds on the Time Complexity of Infinite-Domain CSPsIn Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP-2015) 2015
- Precise Upper and Lower Bounds for the Monotone Constraint Satisfaction ProblemIn Proceedings of the Mathematical Foundations of Computer Science 2015 (MFCS-2015) 2015
2014
- Polynomially Closed Co-ClonesIn Proceedings of the 44th International Symposium on Multiple-Valued Logic (ISMVL-2014) 2014
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time HypothesisIn Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) 2014
2013
- Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint SatisfactionIn Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013) 2013
- Complexity of SAT Problems, Clone Theory and the Exponential Time HypothesisIn Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013) 2013