Login
Computer Science @ Rochester
Tuesday, April 03, 2012
1:00 PM
Computer Science Bldg. Room 703
Ph.D. Thesis Proposal
Curtis Menton
University of Rochester
Manipulation of Elections: Algorithms and Complexity
The thesis of this dissertation will be that complexity and algorithms, used appropriately, are important factors in assessing the value and uses of election systems.

The chapter on search versus decision will point out the importance of that "appropriately"; it proves that unless integer factoring is easy, the standard definitions of manipulability do not capture what they were designed to capture. Other chapters will use 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---some already in hand and some still to be obtained---expected from those chapters 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 strengthening what is known about when unweighted coalition manipulation is hard even when the number of manipulators is constant-bounded. Such results will better allow choosers of election methods to match the protections of the systems they choose with the types of attacks to which those systems are likely to be subjected.