35 citations · 200 across the 47 of their papers we have counts for
3 papers · 1 filter
Anyone but Him: The Complexity of Precluding an Alternative
Edith Hemaspaandra, Lane A. Hemaspaandra, Joerg Rothe
Preference aggregation in a multiagent setting is a central issue in both human and computer contexts. In this paper, we study in terms of complexity the vulnerability of preferenc…
An Exact 2.9416^n Algorithm for the Three Domatic Number Problem
Tobias Riege, Jörg Rothe
The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the verte…
Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory
Lane A. Hemaspaandra, Joerg Rothe, Amitabh Saxena
Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvert…