5 papers
Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students
Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan
This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theore…
Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
Ambiguity-bounded versions of , denoted , bound by the number of accepting paths the nondeterministic polynomial-time Turing machine ca…
Axiomatic Tools for Separating Electoral Control Types, with Applications to Concrete Systems
Michael C. Chavrimootoo, Ian Clingerman, Ethan Ferland +6
Electoral control is the study of whether an attacker, by structural changes on an election such as adding/deleting/partitioning voters or candidates, can affect the winner in some…
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…
Search versus Search for Collapsing Electoral Control Types
Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3
Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [BTT92]. We say two compatible (i.e., having th…