Login
Computer Science @ Rochester
Monday, April 08, 2013
12:00 PM
CBS Room 703
Curtis Menton
University of Rochester
Attacking and Defending Popular Election Systems
The theme of this talk, and dissertation, is that complexity and algorithms, used appropriately, are important factors in assessing the value and uses of election systems. This thesis's work on search versus decision points out the importance of that "appropriately" by proving that unless integer factoring is easy, the standard definitions of manipulability do not capture what they were designed to capture. Other work in this thesis uses complexity and algorithms to analyze the complexity of various types of manipulative attacks on elections, as a way of understanding how computationally vulnerable election systems are. Among the contributions of that other work are: showing that a type of range voting is the most control-attack resistant among all currently analyzed natural election systems; exploring for the first time the detailed control complexity of Schulze elections; and exploring the parameterized complexity of manipulative actions in Schulze and ranked-pairs elections. Such results will better allow choosers of election methods to match the protections of the systems they choose with the types of attack that are of greatest concern.