Publications
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), Aachen, Germany.
A note on X-rays of permutations and a problem of Brualdi and Fritscher
G. Nordh, July 2017, arXiv:1707.03928 [math.CO]
A Note on the Power of Non-Deterministic Circuits with Gate Restrictions
G. Nordh, May 2017, arXiv:1705.03263 [cs.CC]
Polymorphisms and Circuit Complexity
G. Nordh, September 2016, arXiv:1609.04274 [cs.CC]
Strong Partial Clones and the Time Complexity of SAT Problems
P. Jonsson, V. Lagerkvist, G. Nordh, and Bruno Zanuttini, Journal of Computer and System Sciences 84 (2017), pp. 52-78.
Constructing NP-intermediate Problems by Blowing Holes with Parameters of Various Properties
P. Jonsson, V. Lagerkvist, and G. Nordh, Theoretical Computer Science 581 (2015), pp. 67-82.
Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
P. Jonsson, V. Lagerkvist, G. Nordh, B. Zanuttini, In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2013), pp. 1264-1277,
New Orleans, USA.
Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction
P. Jonsson, V. Lagerkvist, G. Nordh, In Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP-2013), pp. 398-414,
Uppsala, Sweden.
Trichotomies in the Complexity of Minimal Inference
A. Durand, M. Hermann, and G. Nordh, Theory of Computing Systems 50(3) (2012), pp. 446-491.
A Note on the Hardness of Skolem-type Sequences
G. Nordh, Discrete Applied Mathematics 158(8) (2010), pp. 964-966.
Retractions to Pseudoforests
T. Feder, P. Hell, P. Jonsson, A. Krokhin, and G. Nordh, SIAM Journal on Discrete Mathematics 24(1) (2010), pp. 101-112.
Approximability of clausal constraints
P. Jonsson and G. Nordh, Theory of Computing Systems 46(2) (2010), pp. 370-395.
Trichotomy in the Complexity of Minimal Inference
A. Durand, M. Hermann, and G. Nordh, In Proceedings of the 24th IEEE Symposium on Logic in Computer Science (LICS-2009), pp. 387-396,
Los Angeles, USA.
Frozen Boolean partial co-clones
G. Nordh and B. Zanuttini, In Proceedings of the 39th International Symposium on Multiple-Valued Logic
(ISMVL-2009), pp. 120-125, Okinawa, Japan.
Integer Programming with 2-Variable Equations and 1-Variable Inequalities
M. Bodirsky, G. Nordh, and T. von Oertzen, Information Processing Letters 109(11) (2009), pp. 572-575.
Introduction to the Maximum Solution Problem
P. Jonsson and G. Nordh, In the survey collection Complexity of Constraints edited by Nadia Creignou,
Phokion G. Kolaitis, and Heribert Vollmer. Springer LNCS 5250, pp. 255-282, 2008.
What makes propositional abduction tractable
G. Nordh and B. Zanuttini, Artificial Intelligence 172(10) (2008), pp. 1245-1284.
Max Ones generalised to larger domains
P. Jonsson, F. Kuivinen, and G. Nordh, SIAM Journal on Computing 38(1) (2008), pp. 329-365.
Perfect Skolem sets
G. Nordh, Discrete Mathematics 308(9) (2008), pp. 1653-1664.
The Maximum Solution Problem on Graphs
P. Jonsson, G. Nordh, and J. Thapper, In Proceedings of the 32nd International Symposium on
Mathematical Foundations of Computer Science (MFCS-2007), pp. 228-239, Cesky Krumlov, Czech Republic.
NP-completeness of generalized multi-Skolem sequences
G. Nordh, Discrete Applied Mathematics 155(16) (2007), pp. 2061-2068.
Complexity Dichotomies for CSP-related Problems
G. Nordh, Linköping Studies In Science And Technology, PhD Dissertation no 1091, 2007. (Defended 1 June 2007)
Approximability of Integer Programming with Generalised Constraints
P. Jonsson, F. Kuivinen, and G. Nordh, In Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming (CP-2006), pp. 256-270, Nantes, France.
Generalised Integer Programming Based on Logically Defined Relations
P. Jonsson and G. Nordh, In Proceedings of the 31st International Symposium on
Mathematical Foundations of Computer Science (MFCS-2006), pp. 549-560, Stará Lesná, Slovak Republic.
The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
G. Nordh, Theoretical Computer Science 345(2-3) (2005), pp. 406-424.
Propositional Abduction is Almost Always Hard
G. Nordh and B. Zanuttini, In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-2005), pp. 534-539,
Edinburgh, Scotland, 2005.
A Trichotomy in the Complexity of Propositional Circumscription
G. Nordh, In Proceedings of the 11th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR-2004), pp. 257-269, Montevideo, Uruguay, 2005.
The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups
G. Nordh, In Proceedings of the 29th International Symposium on
Mathematical Foundations of Computer Science (MFCS-2004), pp. 380-391, Prague, Czech Republic, 2004.
The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups
G. Nordh and P. Jonsson, In Proceedings of the 10th International Computing and Combinatorics Conference (COCOON-2004), pp. 370-379, Jeju Island, Republic of Korea, 2004.
An Algebraic Approach to the Complexity of Propositional Circumscription
G. Nordh and P. Jonsson, In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS-2004), pp. 367-376, Turku, Finland, 2004.
Generalization of Skolem Sequences
G. Nordh, Master's Thesis LITH-MAT-EX-2003/05, Department of Mathematics, Linköpings universitet, 2003.
