Researcher: Ryan O'Donnell
Cross Cutting Thrusts: Formal Methods
The research will study three related issues regarding "fault tolerance" in the theory of voting and in distributed computation: 1) Stability of election-schemes when votes are mis-recorded; 2) fault-resistant leader-election and coin-flipping in distributed computations; and 3) malapportionment and gerrymandering.
These topics will be studied from an algorithmic (and mathematical) perspective - the goals are to understand the benefits and limitations of current methods and to design new voting, leader-election/coin-flipping and apportionment algorithms with better fault-tolerance.
Stability of Election Schemes: Any sufficiently large real-life election will suffer from the problem of misrecorded votes. This is significantly impacted by the voting system being used. In terms of vote corruption, a direct Majority vote election is much more stable than Electoral College voting. We will study this issue from a rigorous standpoint by adopting a probalistic model of votes and errors. These topics will be studied from an algorithmic (and mathematical) perspective - the goals are to understand the benefits and limitations of current methods and to design new voting, leader-election/coin-flipping and apportionment algorithms with better fault-tolerance.
Fault-resistant, Leader-election and Coin-flipping: Instead of the relatively "benign" model of voting errors, one can also consider a more malicious model in which a small group of voters have the ability to arbitrarily change votes. This model is usually studied in the context of distributed computing, with a large number of distributed processors to jointly run a randomized algorithm, using a "leader" that subsequently broadcasts a sequence of random bits to be used. The system can break down however, if some unknown number of the players are faulty. This project look for solutions to this issue, as well as another notable issue related to simpler problem of "collective coin-flipping". Here there is a chance of tolerating an even more malicious sort of fault, in which the processors are adaptively corrupted by a central adversary as the protocol proceeds. This research will seek to improve the protocols associated with this issue.
Malapportionment and Gerrymandering: Apportionment refers to the algorithm for deciding how many seats in a congress should be allocated to each member states, based on the states' population. Malapportionment refers to scenarios in which the number of seats is unfairly skewed. Gerrymandering refers to a related problem, wherein a state's seats are allocated to maliciously skewed geographical districts, so as to increase or decrease the effective voting power of certain groups. Recent research has produced the first efficient algorithm that responds to flaws in previous fault tolerant methods. This project will investigate the simplification of that algorithm and it's incorporation into gerrymandering schemes.