BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Bhaskar DasGupta (UIC) DTSTART:20201208T181500Z DTEND:20201208T184500Z DTSTAMP:20260423T024829Z UID:LA-CoCo/19 DESCRIPTION:Title: Removing partisan bias in redistricting: computational complexity meets t he science of gerrymandering\nby Bhaskar DasGupta (UIC) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nPartisan gerrymanderin g is a major cause for voter disenfranchisement in United States. However\ , convincing US courts to adopt specific measures to quantify gerrymanderi ng has been of limited success to date. Stephanopoulos and McGhee in sever al papers introduced a new measure of partisan gerrymandering via the so-c alled "efficiency gap" that computes the absolute difference of wasted vot es between two political parties in a two-party system\; from a legal poin t of view the measure was found legally convincing in a US appeals court i n a case that claims that the legislative map of the state of Wisconsin wa s gerrymandered. The goal of this talk is to formalize and provide theoret ical and empirical algorithmic analyses of the computational problem of mi nimizing this measure. To this effect\, we show the following:\n\n1. On th e theoretical side\, we formalize the corresponding minimization problem a nd provide non-trivial mathematical and computational complexity propertie s of the problem of minimizing the efficiency gap measure. These are the f irst non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering.\n\n2. On the empirical side\, we provide a sim ple and fast algorithm that can "un-gerrymander" the district maps for the states of Texas\, Virginia\, Wisconsin and Pennsylvania (based on the eff iciency gap measure) by bring their efficiency gaps to acceptable levels f rom the current unacceptable levels. To the best of our knowledge\, ours i s the first publicly available implementation and its corresponding evalua tion on real data for any algorithm for the efficiency gap measure. Our wo rk thus shows that\, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us\, finding district m aps with acceptable levels of efficiency gaps could be a computationally t ractable problem from a practical point of view. Based on these empirical results\, we also provide some interesting insights into three practical i ssues related the efficiency gap measure.\n\nJoint work with Tanima Chatte rjee\, Laura Palmieri\, Zainab Al-Qurashi and Anastasios Sidiropoulos.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/19/ END:VEVENT END:VCALENDAR