Homepage of Gustav Nordh

My current research interests include complexity analysis of constraint problems, combinatorial designs (in particular Skolem-type sequences), and combinatorial optimization.

Contact information

Email: gusno@ida.liu.se
Office: B 3D:454 (map)
Phone: +46 (0)13 282694
Mobile: +46 (0)739 871855

TDDC95 Introduction to the Theory of Computation

Preprints

Trichotomies in the Complexity of Minimal Inference
A. Durand, M. Hermann, and G. Nordh, 2008.

Retractions to Pseudoforests
T. Feder, P. Hell, P. Jonsson, A. Krokhin, and G. Nordh, 2008.

A Note on the Hardness of Skolem-type Sequences
G. Nordh, 2008.

Publications

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.

Approximability of clausal constraints
P. Jonsson and G. Nordh, Theory of Computing Systems. To appear, 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.