BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Amir Yehudayoff (Technion\, Haifa) DTSTART:20201006T163000Z DTEND:20201006T170000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/1 DESCRIPTION:Title: Trichotomy of rates in supervised learning\nby Amir Yehudayoff (Techni on\, Haifa) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstra ct\nWe show that in supervised learning there are only three learning rate s possible: exponential\, linear and arbitrarily slow. Joint work with Bou squet\, Hanneke\, Moran\, and van Handel.\n\nThe talk will be structured f or a general audience\, and is meant to be understood by all.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Javier Tadashi Akagi (National University of Asunción\, San Loren zo\, Paraguay) DTSTART:20201013T171500Z DTEND:20201013T174500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/2 DESCRIPTION:Title: Hard and Easy Instances of L-Tromino Tilings\nby Javier Tadashi Akagi (National University of Asunción\, San Lorenzo\, Paraguay) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nWe study tilings of re gions in the square lattice with L-shaped trominoes. Deciding the existenc e of a tiling with L-trominoes for an arbitrary region in general is NP -complete\, nonetheless\, we identify restrictions to the problem wher e it either remains NP-complete or has a polynomial time algorithm. \n LOCATION:https://researchseminars.org/talk/LA-CoCo/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Jean Cardinal (ULB\, Brussels) DTSTART:20201013T163000Z DTEND:20201013T170000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/3 DESCRIPTION:Title: Flip distances between graph orientations\nby Jean Cardinal (ULB\, Bru ssels) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nF lip graphs encode relations induced on a set of combinatorial objects by e lementary\, local changes. Skeletons of associahedra\, for instance\, are the graphs induced by quadrilateral flips in triangulations of a convex po lygon. For some definition of a flip graph\, a natural computational probl em to consider is the flip distance: Given two objects\, what is the minim um number of flips needed to transform one into the other? We consider the structure and complexity of this problem for orientations of a graph in w hich every vertex has a specified outdegree\, and a flip consists of rever sing all edges of a directed cycle.\n\nJoint work with Oswin Aichholzer\, Tony Huynh\, Kolja Knauer\, Torsten Mütze\, Raphael Steiner\, and Birgit Vogtenhuber.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Christian Ikenmeyer (University of Liverpool) DTSTART:20201006T171500Z DTEND:20201006T174500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/4 DESCRIPTION:Title: The Computational Complexity of Plethysm Coefficients\nby Christian Ik enmeyer (University of Liverpool) as part of LA Combinatorics and Complexi ty Seminar\n\n\nAbstract\nWe show that deciding positivity of plethysm coe fficients is NP-hard\, and that computing plethysm coefficients is #P-hard . In fact\, both problems remain hard even if the inner parameter of the p lethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed\, th en the plethysm coefficient can be computed in polynomial time. Moreover\, we derive new lower and upper bounds and in special cases even combinator ial descriptions for plethysm coefficients\, which is a contribution towar ds Stanley's 9th problem from his list from 1999.\n\nOur technique uses di screte tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer\, Mulmuley\, and Walter (2017). This makes our w ork the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly\, that interpretation also lead s to new equalities between certain plethysm coefficients and Kronecker co efficients.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Vladimir Podolskii (Steklov Mathematical Institute and HSE Univers ity) DTSTART:20201020T163000Z DTEND:20201020T170000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/5 DESCRIPTION:Title: Max-plus polynomials and their roots\nby Vladimir Podolskii (Steklov M athematical Institute and HSE University) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nIn this talk we will discuss polynomials over max-plus semiring and their roots. Max-plus polynomial is basically a piece-wise linear convex function and the roots are points of non-smooth ness of the function. We will discuss analogs of Combinatorial Nullstellen satz\, Schwartz-Zippel Lemma and Universal Testing Set for max-plus polyno mials.\n\nThe talk is aimed at the general audience.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/5/ END:VEVENT BEGIN:VEVENT SUMMARY:Markus Bläser (Saarland University) DTSTART:20201020T171500Z DTEND:20201020T174500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/6 DESCRIPTION:Title: Variety Membership Testing\, Algebraic Natural Proofs\, and Geometric Comp lexity Theory\nby Markus Bläser (Saarland University) as part of LA C ombinatorics and Complexity Seminar\n\n\nAbstract\nWe study the variety me mbership testing problem in the case when the variety is given as an orbit closure and the ambient space is the space of all $3$-tensors. The first variety that we consider is the slice rank variety\, which consists of all $3$-tensors of slice rank at most $r$. We show that the membership testin g problem for the slice rank variety is NP-hard. While the slice ra nk variety is a union of orbit closures\, we define another variety\, the minrank variety\, expressible as a single orbit closure. We also prove the NP-hardness of membership testing in the minrank variety\, establi shing the NP-hardness of the orbit closure containment problem for $3$-tensors.\n\nAlgebraic natural proofs were recently introduced by Forbe s\, Shpilka and Volk and independently by Grochow\, Kumar\, Saks and Saraf . We prove that there are no polynomial algebraic natural proofs for testi ng membership in the slice rank and minrank variety unless coNP is a subset of exists-BPP.\n\nThe talk is aimed at the general audienc e.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/6/ END:VEVENT BEGIN:VEVENT SUMMARY:Aris Filos-Ratsikas (University of Liverpool) DTSTART:20201027T163000Z DTEND:20201027T170000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/7 DESCRIPTION:Title: The Complexity of Necklace Splitting\, Consensus-Halving and Discrete Ham Sandwich\nby Aris Filos-Ratsikas (University of Liverpool) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nThe Necklace Spl itting problem and its continuous counterpart\, the Consensus-Halvi ng problem\, as well as the Discrete Ham Sandwich problem\, are classical problems in combinatorics\, with applications to fair division and social choice theory. A distinctive characteristic of these problems is that they always have a solution\, but it was not known until recently whether such a solution can be found efficiently. We study the computation al complexity of these problems and show that they are complete for the co mputational class PPA. A direct implication of this result is that the problems are unlikely to be solvable in polynomial time.\n\nP.S. For p apers\, see https://arxiv.org/abs/1711.04503 and https://arxiv.org/abs/180 5.12559\n LOCATION:https://researchseminars.org/talk/LA-CoCo/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Joshua Grochow (University of Colorado at Boulder) DTSTART:20201124T181500Z DTEND:20201124T184500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/8 DESCRIPTION:Title: Designing Strassen's algorithm for matrix multiplication\nby Joshua Gr ochow (University of Colorado at Boulder) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nIn 1969\, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear\, the key gain was made by showing that $2 \\times 2$ matrix mu ltiplication could be performed with only $7$ multiplications instead of $ 8$. The latter construction was arrived at by a process of elimination and appears to come out of thin air. We give a transparent proof of this algo rithm using only a simple unitary $2$-design (coming from an irreducible r epresentation of a finite group) and a few easy lines of calculation. More over\, using basic facts from the representation theory of finite groups\, we use $2$-designs coming from group orbits to generalize our constructio n to all $n$ (although the resulting algorithms aren't optimal for $n \\ge 3$). \n\nThe talk will include background on matrix multiplication\, and we'll be able to give the full proof. Based on joint work with C. Moore.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Peter Bürgisser (TU Berlin) DTSTART:20201110T173000Z DTEND:20201110T180000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/9 DESCRIPTION:Title: Complexity of computing zeros of structured polynomial systems\nby Pet er Bürgisser (TU Berlin) as part of LA Combinatorics and Complexity Semin ar\n\n\nAbstract\nCan we solve polynomial systems in polynomial time? Thi s question\nreceived different answers in different contexts. The NP-completeness\nof deciding the feasibility of a general polynomial syste m in both\nTuring and BSS models of computation is certainly an important\ ndifficulty but it does not preclude efficient algorithms for\ncomputing a ll the roots of a polynomial system or solving\npolynomial systems with as many equations as variables\, for which the\nfeasibility over algebraical ly closed fields is granted under\ngenericity hypotheses. And indeed\, th ere are several ways of\ncomputing all $\\delta^n$ zeros of a generic poly nomial system of $n$\nequations of degree $\\delta > 1$ in $n$ variables w ith\n$\\operatorname{poly}(\\delta^n)$ arithmetic operations. \n\nSmale 's 17th problem is a clear-cut formulation\nof the problem in a numeri cal setting. It asks for an algorithm\, with\npolynomial average complexi ty\, for computing one approximate zero of a\ngiven polynomial syst em\, where the complexity is to be measured with\nrespect to the dense input size $N$\, that is\, the number of\npossible monomials in the in put system.\n\nWe design a probabilistic algorithm that\, on input $\\epsi lon>0$ and a polynomial\n system $F$ given by black-box evaluation functi ons\, outputs an approximate\n zero of $F$\, in the sense of Smale\, with probability at least $(1-\\epsilon)$.\n When applying this algorithm to $u \\cdot F$\, where $u$ is uniformly random in\n the product of unitary groups\, the algorithm performs\n $\\operatorname{poly}(n\, \\delta) \\cd ot L(F) \\cdot \\left( \\Gamma(F) \\log \\Gamma(F) + \\log \\log \\epsilon ^{-1} \\right)$\n operations on average. Here $n$ is the number of variab les\, $\\delta$ the\n maximum degree\, $L(F)$ denotes the evaluation cost of $F$\, and $\\Gamma(F)$\n reflects an aspect of the numerical conditio n of $F$. Moreover\, we prove that\n for inputs given by random Gaussian algebraic branching programs of\n size $\\operatorname{poly}(n\,\\delta)$ \, the algorithm runs on average in time\n polynomial in $n$ and $\\delta $. Our result may be interpreted as an\n affirmative answer to a refined version of Smale's 17th problem\, concerned\n with systems of structur ed polynomial equations.\n\nThis is joint work with Felipe Cucker and Pierre Lairez. \nThe talk will not go into technical details and will be accessible to the general audience.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Meirav Zehavi (BGU\, Beersheba) DTSTART:20201117T173000Z DTEND:20201117T180000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/10 DESCRIPTION:Title: Computation of Hadwiger Number and Related Contraction Problems: Tight Lo wer Bounds\nby Meirav Zehavi (BGU\, Beersheba) as part of LA Combinato rics and Complexity Seminar\n\n\nAbstract\nWe prove that the Hadwiger numb er of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) cannot be computed in time $n^{o(n)}$\, unless the Exponential Time Hypoth esis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Ha dwiger number problem has a wider applicability. We use it to rule out the existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs.\n\nJoint wo rk with Fomin\, Lokshtanov\, Mihajlin and Saurabh.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Arnaud de Mesmay (LIGM\, Université Paris Est) DTSTART:20201103T173000Z DTEND:20201103T180000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/11 DESCRIPTION:Title: Link crossing number is NP-hard\nby Arnaud de Mesmay (LIGM\, Universi té Paris Est) as part of LA Combinatorics and Complexity Seminar\n\n\nAbs tract\nMost invariants in knot theory are very hard to compute in practice \, yet only few computational hardness proofs are known. In this talk\, we survey the computational complexity of many problems coming from knot the ory\, emphasizing the numerous open problems\, and we present a proof of N P-hardness for the crossing number of a link.\n\nJoint work with Marcus Sc haefer and Eric Sedgwick.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/11/ END:VEVENT BEGIN:VEVENT SUMMARY:Cris Moore (Santa Fe Institute) DTSTART:20201117T181500Z DTEND:20201117T184500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/12 DESCRIPTION:Title: Percolation is Odd\nby Cris Moore (Santa Fe Institute) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nIn site percolation\, a spanning configuration is a set of vertices that includes a path from th e top of a lattice to the bottom. We prove that for square lattices of any height and width\, the number of spanning configurations with an odd or e ven number of vertices differs by ±1. In particular\, the total number of spanning configurations is always odd. (You may enjoy working out the pro of on your own before the talk!) This result holds also for the hypercubic lattice in any dimension\, with a wide variety of boundary conditions. \n \nThis is joint work with Stephan Mertens.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/12/ END:VEVENT BEGIN:VEVENT SUMMARY:Zuzana Patáková (Charles University\, Prague) DTSTART:20201103T181500Z DTEND:20201103T184500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/13 DESCRIPTION:Title: Shellability is NP-complete\nby Zuzana Patáková (Charles University \, Prague) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstrac t\nShellabi lity is an important notion that lead to such mathematical discove ries as the Dehn-Sommerville relations\, the\nUpper Bound Theorem\, and ch aracterization of topology of the Bruhat order.\nRoughly speaking\, a simp licial complex is shellable if it can be build\ninductively while controll ing its topological properties.\nIn this talk we show that starting from d imension two\, deciding\nshellability is NP-complete.\n\nJoint work with Xavier Goaoc\, Pavel Paták\, Martin Tancer\, and Uli\nWagner.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Yuri Rabinovich (University of Haifa) DTSTART:20201201T173000Z DTEND:20201201T180000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/14 DESCRIPTION:Title: Large simple cycles in dense simplicial complexes\nby Yuri Rabinovich (University of Haifa) as part of LA Combinatorics and Complexity Seminar\ n\n\nAbstract\nSimplicial complexes can be viewed as a higher dimensional generalization of graphs\nwith a significantly richer structure than hyper graphs. For example\, many graph theoretic\nnotions such as cycles\, cuts\ , eigenvalues\, etc.\, have natural analogues in\nsimplicial complexes\, a s opposed to hypergraphs. Moreover\, in addition to Combinatorics\,\npower ful methods from Linear Algebra\, Matroid Theory\, Algebraic Topology\, et c.\,\ncan be $-$ and are $-$ employed in their study. \n\nIn the recent de cades there has been a\nsignificant progress in the study of random simpli cial complexes\, as well as in\nunderstanding their extremal properties. T here are also some startling\napplications to Computer Science yet to be d eveloped. \nThat said\, there remain many natural and seemingly simple ope n problems in the theory of simplicial complexes. Here we focus on one suc h problem\, which on a closer inspection turns out to be interesting and n ontrivial.\n\nA classical theorem of Erdős and Gallai (1959)\, asserts th at for an\nundirected graph $G=(V\,E)$\, if $|E| > 2k(|V|-1)$\, then $G$ c ontains a cycle of length $> k$.\nIn other words\, the density of graph is a lower bound for the size of the largest cycle in it\, up to a co nstant factor. We show that the size of the largest simple $d$-cycle in a simplicial $d$-complex is at least a square root of its density.\n\n Ba sed on a joint work with Roy Meshulam and Ilan Newman.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/14/ END:VEVENT BEGIN:VEVENT SUMMARY:Igor Shinkar (Simon Fraser University) DTSTART:20201027T171500Z DTEND:20201027T174500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/15 DESCRIPTION:Title: On Percolation and NP-Hardness\nby Igor Shinkar (Simon Fraser Univers ity) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nWe study the computational complexity of problems whose inputs are obtained b y applying random noise to worst-case instances. For an appropriate notion of noise we show that a number of classical NP-complete problems o n graphs remain essentially as hard on the noisy instances as they are in the worst-case.\n\nFocusing on the Graph Coloring problem\, we esta blish the following result: Given a graph $G$\, consider a random subgraph of $G$ obtained by deleting the edges of $G$ independently with probabili ty $0.5$. We show that if the chromatic number of $G$ is large\, then with high probability the chromatic number of the random subgraph remains larg e. That is the chromatic number of any graph is ``robust'' to random edge deletions.\n\nJoint work with Huck Bennett and Daniel Reichman.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/15/ END:VEVENT BEGIN:VEVENT SUMMARY:Yuval Filmus (Technion\, Haifa\, Israel) DTSTART:20201124T173000Z DTEND:20201124T180000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/16 DESCRIPTION:Title: Sauer–Shelah–Perles lemma for lattices\nby Yuval Filmus (Technion \, Haifa\, Israel) as part of LA Combinatorics and Complexity Seminar\n\n\ nAbstract\nThe Sauer–Shelah–Perles (SSP) lemma is a fund amental result in VC theory\, with important applications in statistical l earning theory. It bounds the number of sets in a family in terms of the size of the universe and the VC dimension. We generalize the SSP lemma to some lattices\, such as the lattice of subspaces of a finite-dimensional vector space over a finite field. The SSP lemma fails for some lattices\, and we identify a local obstruction which we conjecture is the only reaso n for such failure.\n\nThe talk will not assume any familiarity with VC th eory or with statistical learning theory.\n\nJoint work with Stijn Cambie (Raboud University Nijmegen)\, Bogdan Chornomaz (Vanderbilt University)\, Zeev Dvir (Princeton University) and Shay Moran (Technion).\n LOCATION:https://researchseminars.org/talk/LA-CoCo/16/ END:VEVENT BEGIN:VEVENT SUMMARY:Christoph Haase (UCL\, London) DTSTART:20201110T181500Z DTEND:20201110T184500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/17 DESCRIPTION:Title: On the size of finite rational matrix semigroups\nby Christoph Haase (UCL\, London) as part of LA Combinatorics and Complexity Seminar\n\n\nAbs tract\nGiven a finite set of $n \\times n$ integer matrices $\\mathcal M$ that\ngenerate a finite multiplicative semigroup $\\overline{\\mathcal M}$ \, I am\ngoing to present a recent result showing that any $M \\in\n\\over line{\\mathcal M}$ is a product of at most $2^{O(n^2 \\log n)}$\nelements from $\\mathcal M$. This bound immediately implies a bound on\nthe cardina lity of $\\overline{\\mathcal M}$.\n\nI will provide a non-technical proof sketch demonstrating how the\naforementioned bound can be obtained. In ad dition\, I will discuss the\nhistory of this problem\, its motivation\, wh ich is rooted in automata\ntheory\, related results that have appeared ove r the last decades\, and\nopen challenges.\n\nThe talk is based on joint w ork with Georgina Bumpus\, Stefan Kiefer\,\nPaul-Ioan Stoienescu and Jonat han Tanner from Oxford\, which appeared at\nICALP'20\n LOCATION:https://researchseminars.org/talk/LA-CoCo/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Giovanni Paolini (AWS and Caltech) DTSTART:20201201T181500Z DTEND:20201201T184500Z DTSTAMP:20260422T225922Z UID:LA-CoCo/18 DESCRIPTION:Title: How to collapse a simplicial complex: theory and practice\nby Giovann i Paolini (AWS and Caltech) as part of LA Combinatorics and Complexity Sem inar\n\n\nAbstract\nSometimes one wants to answer topological questions ab out a simplicial complex: Is it contractible? Does it deformation retract onto a certain subcomplex? What is its homotopy type? What is its homology ? In this talk\, I will introduce discrete Morse theory\, which allows app roaching these questions in a purely combinatorial way\, by constructing s equences of "elementary collapses" between pairs of simplices. Then I will outline algorithms and hardness results for collapsibility and discrete M orse theory.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/18/ END:VEVENT BEGIN:VEVENT SUMMARY:Bhaskar DasGupta (UIC) DTSTART:20201208T181500Z DTEND:20201208T184500Z DTSTAMP:20260422T225922Z 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 BEGIN:VEVENT SUMMARY:Dustin G. Mixon (OSU) DTSTART:20201208T190000Z DTEND:20201208T193000Z DTSTAMP:20260422T225922Z UID:LA-CoCo/20 DESCRIPTION:Title: The Mathematics of Partisan Gerrymandering\nby Dustin G. Mixon (OSU) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nEvery de cade\, politicians update voting districts to account for population shift s as measured by the U.S. Census. Of course\, partisan politicians are inc lined to draw maps that favor their own party\, resulting in partisan gerr ymandering. In this talk\, we will explore how tools from mathematics can help to deter this growing threat to democracy.\n\nOur main result is that deciding whether there exists a fair redistricting among legal maps is NP-hard. Joint work with Richard Kueng and Soledad Villar.\n LOCATION:https://researchseminars.org/talk/LA-CoCo/20/ END:VEVENT END:VCALENDAR