1 citations · 1 across the 5 of their papers we have counts for
6 papers
On the Strength of Uniqueness Quantification in Primitive Positive Formulas
Victor Lagerkvist, Gustav Nordh
Uniqueness quantification () is a quantifier in first-order logic where one requires that exactly one element exists satisfying a given property. In this paper we invest…
A note on X-rays of permutations and a problem of Brualdi and Fritscher
Gustav Nordh
The subject of this note is a challenging conjecture about X-rays of permutations which is a special case of a conjecture regarding Skolem sequences. In relation to this, Brualdi a…
A Note on the Power of Non-Deterministic Circuits with Gate Restrictions
Gustav Nordh
We investigate the power of non-deterministic circuits over restricted sets of base gates. We note that the power of non-deterministic circuits exhibit a dichotomy, in the followin…
Polymorphisms and Circuit Complexity
Gustav Nordh
We present a framework for studying circuit complexity that is inspired by techniques that are used for analyzing the complexity of CSPs. We prove that the circuit complexity of a…
Approximability of Integer Programming with Generalised Constraints
Peter Jonsson, Fredrik Kuivinen, Gustav Nordh
We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables…
Perfect Skolem sets
Gustav Nordh
A Skolem sequence is a sequence a_1,a_2,...,a_2n (where a_i \in A = {1,...,n }), each a_i occurs exactly twice in the sequence and the two occurrences are exactly a_i positions apa…