COLLOQUIUM: Wendy Cho, "Massively Parallel Evolutionary Computation for Empowering Electoral Reform: Quantifying Gerrymandering via Multi-Objective Optimization and Statistical Analysis"

Event Type

Seminar/Symposium

Sponsor

Illinois Computer Science

Virtual

Date

Sep 28, 2020   3:30 pm  

Views

173

Originating Calendar

Computer Science Speakers Calendar

Abstract:
Important insights into redistricting can be gained by formulating and analyzing the problem within a large-scale spatial optimization and sampling framework. Redistricting is an application of the graph-partitioning problem that is NP-Hard.  We develop an Evolutionary Markov Chain Monte Carlo (EMCMC) algorithm for sampling spatial partitions that lie within a large, complex, and constrained spatial state space. Our algorithm combines the advantages of evolutionary algorithms as optimization heuristics for state space traversal and the theoretical convergence properties of Markov Chain Monte Carlo algorithms for sampling from unknown distributions. Local optimality information that is identified via a directed search by our optimization heuristic is used to adaptively update a Markov chain in a promising direction within the framework of a Multiple-Try Metropolis Markov Chain model that incorporates a generalized Metropolis-Hastings ratio. We further expand the reach of our EMCMC algorithm by harnessing the computational power afforded by massively parallel computing architecture through the integration of a parallel EA framework that guides Markov chains running in parallel. We experimentally demonstrate the effectiveness of our algorithm to utilize hundreds of thousands of processors for the redistricting problem.  The massive computing power allows us to extract new substantive insights that closely mesh with the framework that the Supreme Court has elucidated for electoral reform.

Bio:
Wendy K. Tam Cho is Professor in the Departments of Political Science, Statistics, Mathematics, Asian American Studies, the College of Law, and the National Center for Supercomputing Applications, a Guggenheim Fellow, Faculty in the Illinois Informatics Institute, and Affiliate of the Cline Center for Democracy, the Computational Science and Engineering Program, and the Program on Law, Behavior, and Social Science, at the University of Illinois at Urbana-Champaign. 

Faculty Host: Tandy Warnow