Author name cluster

Henning Schnoor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

ECAI Conference 2016 Conference Paper

Dichotomy for Pure Scoring Rules Under Manipulative Electoral Actions

Edith Hemaspaandra
Henning Schnoor

Scoring systems are an extremely important class of election systems. We study the complexity of manipulation, constructive control by deleting voters (CCDV), and bribery for scoring systems. For manipulation, we show that for all scoring rules with a constant number of different coefficients, manipulation is in P. And we conjecture that there is no dichotomy theorem.

Details

CSL Conference 2015 Conference Paper

A Van Benthem Theorem for Modal Team Semantics

Juha Kontinen
Julian-Steffen Müller
Henning Schnoor
Heribert Vollmer

The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework of modal dependence logic (MDL) and team semantics. We show that Modal Team Logic (MTL) extending MDL by classical negation captures exactly the FO-definable bisimulation invariant properties of Kripke structures and teams. We also compare the expressive power of MTL to most of the variants and extensions of MDL recently studied in the area.

Details

AAAI Conference 2014 Conference Paper

A Control Dichotomy for Pure Scoring Rules

Edith Hemaspaandra
Lane Hemaspaandra
Henning Schnoor

Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are “family-like” is the recently introduced notion of (polynomial-time uniform) pure scoring rules (Betzler and Dorn 2010), where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k ≤ 3, k-veto with k ≤ 2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a “hybrid” of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be “w. l. o. g. ” in fact do lose generality.

PDF Details

MFCS Conference 2013 Conference Paper

Noninterference with Local Policies

Sebastian Eggert
Henning Schnoor
Thomas Wilke

Abstract We develop a theory for state-based noninterference in a setting where different security policies—we call them local policies—apply in different parts of a given system. Our theory comprises appropriate security definitions, characterizations of these definitions, for instance in terms of unwindings, algorithms for analyzing the security of systems with local policies, and corresponding complexity results.

Details

ECAI Conference 2012 Conference Paper

Weighted Manipulation for Four-Candidate Llull Is Easy

Piotr Faliszewski
Edith Hemaspaandra
Henning Schnoor

Our main contribution is a surprising polynomial-time algorithm for weighed coalitional manipulation of four-candidate Copeland (also known as Llull) elections. On the technical side, our algorithm relies on a polynomial-time routine that solves a variant of the partition problem. We also show that there is a pseudopolynomial-time algorithm for weighted coalitional manipulation with a fixed number of candidates under any anonymous rule with a polynomial-time winner-determination procedure.

Details

MFCS Conference 2011 Conference Paper

A Universally Defined Undecidable Unimodal Logic

Edith Hemaspaandra
Henning Schnoor

Abstract Modal logics are widely used in computer science. The complexity of their satisfiability problems has been an active field of research since the 1970s. We prove that even very “simple” modal logics can be undecidable: We show that there is an undecidable unimodal logic that can be obtained by restricting the allowed models with an equality-free first-order formula in which only universal quantifiers appear.

Details

IJCAI Conference 2011 Conference Paper

Minimization for Generalized Boolean Formulas

Edith Hemaspaandra
Henning Schnoor

The minimization problem for propositional formulas is an important optimization problem in the second level of the polynomial hierarchy. In general, the problem is Sigma-2-complete under Turing reductions, but restricted versions are tractable. We study the complexity of minimization for formulas in two established frameworks for restricted propositional logic: The Post framework allowing arbitrarily nested formulas over a set of Boolean connectors, and the constraint setting, allowing generalizations of CNF formulas. In the Post case, we obtain a dichotomy result: Minimization is solvable in polynomial time or coNP-hard. This result also applies to Boolean circuits. For CNF formulas, we obtain new minimization algorithms for a large class of formulas, and give strong evidence that we have covered all polynomial-time cases.

PDF Details DOI

AAMAS Conference 2010 Conference Paper

Manipulation of Copeland Elections

Piotr Faliszewski
Edith Hemaspaandra
Henning Schnoor

We resolve an important open problem regarding the complexity of (constructive) unweighted coalitional manipulation problem in Copeland$^\alpha$ elections, that is, the complexity of Copeland$^\alpha$-manipulation for alpha in {0, 1}. Copeland$^\alpha$, $0 \le \alpha \le 1$, is an election system where for each pair of candidates we check which one is preferred by more voters (i. e. , we conduct a head-to-head majority contest) and we give one point to this candidate and zero to the other. However, in case of a tie both candidates receive alpha points. In the end, candidates with most points win. It is known that Copeland$^\alpha$-manipulation is NP-complete for all rational alpha's in [0, 1]-{0. 5} (i. e. , for all the reasonable cases except the three truely interesting ones). In this paper we show that the problem remains NP-complete for $\alpha \in {0, 1}$. In addition, we resolve the complexity of Copeland$^\alpha$-manipulation for each rational $\alpha \in [0, 1]$ for the case of irrational voters.

PDF

AAMAS Conference 2010 Conference Paper

Strategic Planning for Probabilistic Games with Incomplete Information

Henning Schnoor

Alternating-time Temporal Logic (ATL) is widely used to reason about strategic abilities of players. Aiming at strategies that can realistically be implemented in software, many variants of ATL study a setting with incomplete information, where strategies may only take available information into account. Another generalization of ATL is Probabilistic ATL, where strategies are required to achieve their goal with a certain probability. We introduce a semantics of ATL that takes into account both of these aspects. We prove that our semantics allows simulation relations similar in spirit to usual bisimulations, and has a decidable model checking problem (in the case of memoryless strategies, with memory-dependent strategies the problem is undecidable).

PDF

AAMAS Conference 2008 Conference Paper

Copeland Voting: Ties Matter

Piotr Faliszewski
Edith Hemaspaandra
Henning Schnoor

We study the complexity of manipulation for a family of election systems derived from Copeland voting via introducing a parameter α that describes how ties in head-to-head contests are valued. We show that the thus obtained problem of manipulation for unweighted Copelandα elections is NP-complete even if the size of the manipulating coalition is limited to two. Our result holds for all rational values of α such that 0 < α < 1 except for α = 1 2. Since it is well known that manipulation via a single voter is easy for Copeland, our result is the first one where an election system originally known to be vulnerable to manipulation via a single voter is shown to be resistant to manipulation via a coalition of a constant number of voters. We also study the complexity of manipulation for Copelandα for the case of a constant number of candidates. We show that here the exact complexity of manipulation often depends closely on the α: Depending on whether we try to make our favorite candidate a winner or a unique winner and whether α is 0, 1 or between these values, the problem of weighted manipulation for Copelandα with three candidates is either in P or is NP-complete. Our results show that ways in which ties are treated in an election system, here Copeland voting, can be crucial to establishing complexity results for this system.

PDF

CSL Conference 2008 Conference Paper

Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint

Nadia Creignou
Henning Schnoor
Ilka Schnoor

Abstract We study the computational complexity of Boolean constraint satisfaction problems with cardinality constraint. A Galois connection between clones and co-clones has received a lot of attention in the context of complexity considerations for constraint satisfaction problems. This connection fails when considering constraint satisfaction problems that support in addition a cardinality constraint. We prove that a similar Galois connection, involving a weaker closure operator and partial polymorphisms, can be applied to such problems. Thus, we establish dichotomies for the decision as well as for the counting problems in Schaefer’s framework.

Details

MFCS Conference 2005 Conference Paper

The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Eric Allender
Michael Bauland
Neil Immerman
Henning Schnoor
Heribert Vollmer

Abstract Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer’s dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P ≠ NP). We show that if one considers AC 0 isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

Details