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:20260404T111331Z UID:LA-CoCo/1 DESCRIPTION:Title: Trichotomy of rates in supervised learning\nby Amir Yehudayoff (Technion\, Haifa) as part of LA Combinatorics and Complexity Seminar\n\n\ nAbstract\nWe show that in supervised learning there are only three learni ng rates possible: exponential\, linear and arbitrarily slow. Joint work w ith Bousquet\, Hanneke\, Moran\, and van Handel.\n\nThe talk will be struc tured for a general audience\, and is meant to be understood by all.\n LOCATION:https://stable.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:20260404T111331Z 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 tiling s of regions in the square lattice with L-shaped trominoes. Deciding the e xistence of a tiling with L-trominoes for an arbitrary region in general i s NP-complete\, nonetheless\, we identify restrictions to the probl em where it either remains NP-complete or has a polynomial time alg orithm.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Jean Cardinal (ULB\, Brussels) DTSTART:20201013T163000Z DTEND:20201013T170000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/3 DESCRIPTION:Title: Flip distances between graph orientations\nby Jean Cardinal (UL B\, Brussels) as part of LA Combinatorics and Complexity Seminar\n\n\nAbst ract\nFlip graphs encode relations induced on a set of combinatorial objec ts by elementary\, local changes. Skeletons of associahedra\, for instance \, are the graphs induced by quadrilateral flips in triangulations of a co nvex polygon. For some definition of a flip graph\, a natural computationa l problem to consider is the flip distance: Given two objects\, what is th e minimum number of flips needed to transform one into the other? We consi der the structure and complexity of this problem for orientations of a gra ph in which every vertex has a specified outdegree\, and a flip consists o f reversing all edges of a directed cycle.\n\nJoint work with Oswin Aichho lzer\, Tony Huynh\, Kolja Knauer\, Torsten Mütze\, Raphael Steiner\, and Birgit Vogtenhuber.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Christian Ikenmeyer (University of Liverpool) DTSTART:20201006T171500Z DTEND:20201006T174500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/4 DESCRIPTION:Title: The Computational Complexity of Plethysm Coefficients\nby Chris tian Ikenmeyer (University of Liverpool) as part of LA Combinatorics and C omplexity Seminar\n\n\nAbstract\nWe show that deciding positivity of pleth ysm coefficients is NP-hard\, and that computing plethysm coefficients is #P-hard. In fact\, both problems remain hard even if the inner parameter o f the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fix ed\, then the plethysm coefficient can be computed in polynomial time. Mor eover\, we derive new lower and upper bounds and in special cases even com binatorial descriptions for plethysm coefficients\, which is a contributio n towards Stanley's 9th problem from his list from 1999.\n\nOur technique uses discrete tomography in a more refined way than the recent work on Kro necker coefficients by Ikenmeyer\, Mulmuley\, and Walter (2017). This make s our work the first to apply techniques from discrete tomography to the s tudy of plethysm coefficients. Quite surprisingly\, that interpretation al so leads to new equalities between certain plethysm coefficients and Krone cker coefficients.\n LOCATION:https://stable.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:20260404T111331Z UID:LA-CoCo/5 DESCRIPTION:Title: Max-plus polynomials and their roots\nby Vladimir Podolskii (St eklov Mathematical Institute and HSE University) as part of LA Combinatori cs and Complexity Seminar\n\n\nAbstract\nIn this talk we will discuss poly nomials over max-plus semiring and their roots. Max-plus polynomial is bas ically a piece-wise linear convex function and the roots are points of non -smoothness of the function. We will discuss analogs of Combinatorial Null stellensatz\, Schwartz-Zippel Lemma and Universal Testing Set for max-plus polynomials.\n\nThe talk is aimed at the general audience.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/5/ END:VEVENT BEGIN:VEVENT SUMMARY:Markus Bläser (Saarland University) DTSTART:20201020T171500Z DTEND:20201020T174500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/6 DESCRIPTION:Title: Variety Membership Testing\, Algebraic Natural Proofs\, and Geometr ic Complexity Theory\nby Markus Bläser (Saarland University) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nWe study the var iety membership testing problem in the case when the variety is given as a n 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 testing problem for the slice rank variety is NP-hard. While the s lice rank variety is a union of orbit closures\, we define another variety \, the minrank variety\, expressible as a single orbit closure. We also pr ove the NP-hardness of membership testing in the minrank variety\, establishing the NP-hardness of the orbit closure containment probl em for $3$-tensors.\n\nAlgebraic natural proofs were recently introduced b y Forbes\, Shpilka and Volk and independently by Grochow\, Kumar\, Saks an d Saraf. We prove that there are no polynomial algebraic natural proofs fo r testing membership in the slice rank and minrank variety unless coNP< /b> is a subset of exists-BPP.\n\nThe talk is aimed at the general audience.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/6/ END:VEVENT BEGIN:VEVENT SUMMARY:Aris Filos-Ratsikas (University of Liverpool) DTSTART:20201027T163000Z DTEND:20201027T170000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/7 DESCRIPTION:Title: The Complexity of Necklace Splitting\, Consensus-Halving and Discre te Ham Sandwich\nby Aris Filos-Ratsikas (University of Liverpool) as p art of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nThe Neckl ace Splitting problem and its continuous counterpart\, the Consensu s-Halving problem\, as well as the Discrete Ham Sandwich problem\, are classical problems in combinatorics\, with applications to fair di vision and social choice theory. A distinctive characteristic of these pr oblems is that they always have a solution\, but it was not known until re cently whether such a solution can be found efficiently. We study the comp utational complexity of these problems and show that they are complete for the computational class PPA. A direct implication of this result i s that the problems are unlikely to be solvable in polynomial time.\n\nP.S . For papers\, see https://arxiv.org/abs/1711.04503 and https://arxiv.org/ abs/1805.12559\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Joshua Grochow (University of Colorado at Boulder) DTSTART:20201124T181500Z DTEND:20201124T184500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/8 DESCRIPTION:Title: Designing Strassen's algorithm for matrix multiplication\nby Jo shua Grochow (University of Colorado at Boulder) as part of LA Combinatori cs and Complexity Seminar\n\n\nAbstract\nIn 1969\, Strassen shocked the wo rld by showing that two n x n matrices could be multiplied in time asympto tically less than $O(n^3)$. While the recursive construction in his algori thm is very clear\, the key gain was made by showing that $2 \\times 2$ ma trix multiplication could be performed with only $7$ multiplications inste ad of $8$. The latter construction was arrived at by a process of eliminat ion and appears to come out of thin air. We give a transparent proof of th is algorithm using only a simple unitary $2$-design (coming from an irredu cible representation of a finite group) and a few easy lines of calculatio n. Moreover\, using basic facts from the representation theory of finite g roups\, we use $2$-designs coming from group orbits to generalize our cons truction 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. M oore.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/8/ END:VEVENT BEGIN:VEVENT SUMMARY:Peter Bürgisser (TU Berlin) DTSTART:20201110T173000Z DTEND:20201110T180000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/9 DESCRIPTION:Title: Complexity of computing zeros of structured polynomial systems\ nby Peter Bürgisser (TU Berlin) as part of LA Combinatorics and Complexit y Seminar\n\n\nAbstract\nCan we solve polynomial systems in polynomial tim e? This question\nreceived different answers in different contexts. The NP-completeness\nof deciding the feasibility of a general polynomia l system in both\nTuring and BSS models of computation is certainly an imp ortant\ndifficulty but it does not preclude efficient algorithms for\ncomp uting all the roots of a polynomial system or solving\npolynomial systems with as many equations as variables\, for which the\nfeasibility over alge braically closed fields is granted under\ngenericity hypotheses. And inde ed\, there are several ways of\ncomputing all $\\delta^n$ zeros of a gener ic polynomial system of $n$\nequations of degree $\\delta > 1$ in $n$ vari ables with\n$\\operatorname{poly}(\\delta^n)$ arithmetic operations. \n\n< i>Smale's 17th problem is a clear-cut formulation\nof the problem in a numerical setting. It asks for an algorithm\, with\npolynomial average c omplexity\, for computing one approximate zero of a\ngiven polynomi al system\, where the complexity is to be measured with\nrespect to the dense input size $N$\, that is\, the number of\npossible monomials in the input system.\n\nWe design a probabilistic algorithm that\, on input $\\epsilon>0$ and a polynomial\n system $F$ given by black-box evaluation functions\, outputs an approximate\n zero of $F$\, in the sense of Smale \, with probability at least $(1-\\epsilon)$.\n When applying this algori thm to $u \\cdot F$\, where $u$ is uniformly random in\n the product of u nitary groups\, the algorithm performs\n $\\operatorname{poly}(n\, \\delt a) \\cdot L(F) \\cdot \\left( \\Gamma(F) \\log \\Gamma(F) + \\log \\log \\ epsilon^{-1} \\right)$\n operations on average. Here $n$ is the number of variables\, $\\delta$ the\n maximum degree\, $L(F)$ denotes the evaluati on cost of $F$\, and $\\Gamma(F)$\n reflects an aspect of the numerical c ondition of $F$. Moreover\, we prove that\n for inputs given by random Ga ussian 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 r efined version of Smale's 17th problem\, concerned\n with systems of s tructured polynomial equations.\n\nThis is joint work with Felipe Cuck er and Pierre Lairez. \nThe talk will not go into technical details and w ill be accessible to the general audience.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/9/ END:VEVENT BEGIN:VEVENT SUMMARY:Meirav Zehavi (BGU\, Beersheba) DTSTART:20201117T173000Z DTEND:20201117T180000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/10 DESCRIPTION:Title: Computation of Hadwiger Number and Related Contraction Problems: T ight Lower Bounds\nby Meirav Zehavi (BGU\, Beersheba) as part of LA Co mbinatorics and Complexity Seminar\n\n\nAbstract\nWe prove that the Hadwig er number of an $n$-vertex graph $G$ (the maximum size of a clique minor i n $G$) cannot be computed in time $n^{o(n)}$\, unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the a rea of exact exponential algorithms. The technique developed for resolving the Hadwiger 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 cl ass of computational problems concerning edge contractions in graphs.\n\nJ oint work with Fomin\, Lokshtanov\, Mihajlin and Saurabh.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/10/ END:VEVENT BEGIN:VEVENT SUMMARY:Arnaud de Mesmay (LIGM\, Université Paris Est) DTSTART:20201103T173000Z DTEND:20201103T180000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/11 DESCRIPTION:Title: Link crossing number is NP-hard\nby Arnaud de Mesmay (LIGM\, U niversité Paris Est) as part of LA Combinatorics and Complexity Seminar\n \n\nAbstract\nMost invariants in knot theory are very hard to compute in p ractice\, yet only few computational hardness proofs are known. In this ta lk\, we survey the computational complexity of many problems coming from k not theory\, emphasizing the numerous open problems\, and we present a pro of of NP-hardness for the crossing number of a link.\n\nJoint work with Ma rcus Schaefer and Eric Sedgwick.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/11/ END:VEVENT BEGIN:VEVENT SUMMARY:Cris Moore (Santa Fe Institute) DTSTART:20201117T181500Z DTEND:20201117T184500Z DTSTAMP:20260404T111331Z 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 percola tion\, a spanning configuration is a set of vertices that includes a path from the 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 o dd or even number of vertices differs by ±1. In particular\, the total nu mber of spanning configurations is always odd. (You may enjoy working out the proof on your own before the talk!) This result holds also for the hyp ercubic lattice in any dimension\, with a wide variety of boundary conditi ons. \n\nThis is joint work with Stephan Mertens.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/12/ END:VEVENT BEGIN:VEVENT SUMMARY:Zuzana Patáková (Charles University\, Prague) DTSTART:20201103T181500Z DTEND:20201103T184500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/13 DESCRIPTION:Title: Shellability is NP-complete\nby Zuzana Patáková (Charles Uni versity\, Prague) as part of LA Combinatorics and Complexity Seminar\n\n\n Abstract\nS hellability is an important notion that lead to such mathematical discoveries as the Dehn-Sommerville relations\, the\nUpper Bound Theorem\, and characterization of topology of the Bruhat order.\nRoughly speaking\, a simplicial complex is shellable if it can be build\ninductively while c ontrolling its topological properties.\nIn this talk we show that starting from dimension two\, deciding\nshellability is NP-complete.\n\nJoi nt work with Xavier Goaoc\, Pavel Paták\, Martin Tancer\, and Uli\nWagner .\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/13/ END:VEVENT BEGIN:VEVENT SUMMARY:Yuri Rabinovich (University of Haifa) DTSTART:20201201T173000Z DTEND:20201201T180000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/14 DESCRIPTION:Title: Large simple cycles in dense simplicial complexes\nby Yuri Rab inovich (University of Haifa) as part of LA Combinatorics and Complexity S eminar\n\n\nAbstract\nSimplicial complexes can be viewed as a higher dimen sional generalization of graphs\nwith a significantly richer structure tha n hypergraphs. For example\, many graph theoretic\nnotions such as cycles\ , cuts\, eigenvalues\, etc.\, have natural analogues in\nsimplicial comple xes\, as opposed to hypergraphs. Moreover\, in addition to Combinatorics\, \npowerful methods from Linear Algebra\, Matroid Theory\, Algebraic Topolo gy\, etc.\,\ncan be $-$ and are $-$ employed in their study. \n\nIn the re cent decades there has been a\nsignificant progress in the study of random simplicial complexes\, as well as in\nunderstanding their extremal proper ties. There are also some startling\napplications to Computer Science yet to be developed. \nThat said\, there remain many natural and seemingly sim ple open problems in the theory of simplicial complexes. Here we focus on one such problem\, which on a closer inspection turns out to be interestin g and nontrivial.\n\nA classical theorem of Erdős and Gallai (1959)\, ass erts that for an\nundirected graph $G=(V\,E)$\, if $|E| > 2k(|V|-1)$\, the n $G$ contains a cycle of length $> k$.\nIn other words\, the density o f graph is a lower bound for the size of the largest cycle in it\, up to a constant factor. We show that the size of the largest simple $d$-cyc le in a simplicial $d$-complex is at least a square root of its density.\n \n Based on a joint work with Roy Meshulam and Ilan Newman.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/14/ END:VEVENT BEGIN:VEVENT SUMMARY:Igor Shinkar (Simon Fraser University) DTSTART:20201027T171500Z DTEND:20201027T174500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/15 DESCRIPTION:Title: On Percolation and NP-Hardness\nby Igor Shinkar (Simon Fraser University) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstra ct\nWe study the computational complexity of problems whose inputs are obt ained by applying random noise to worst-case instances. For an appropriate notion of noise we show that a number of classical NP-complete pro blems on graphs remain essentially as hard on the noisy instances as they are in the worst-case.\n\nFocusing on the Graph Coloring problem\, we establish the following result: Given a graph $G$\, consider a random s ubgraph of $G$ obtained by deleting the edges of $G$ independently with pr obability $0.5$. We show that if the chromatic number of $G$ is large\, th en with high probability the chromatic number of the random subgraph remai ns large. That is the chromatic number of any graph is ``robust'' to rando m edge deletions.\n\nJoint work with Huck Bennett and Daniel Reichman.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/15/ END:VEVENT BEGIN:VEVENT SUMMARY:Yuval Filmus (Technion\, Haifa\, Israel) DTSTART:20201124T173000Z DTEND:20201124T180000Z DTSTAMP:20260404T111331Z UID:LA-CoCo/16 DESCRIPTION:Title: Sauer–Shelah–Perles lemma for lattices\nby Yuval Filmus (T echnion\, Haifa\, Israel) as part of LA Combinatorics and Complexity Semin ar\n\n\nAbstract\nThe Sauer–Shelah–Perles (SSP) lemma is a fundamental result in VC theory\, with important applications in statis tical learning 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 l emma to some lattices\, such as the lattice of subspaces of a finite-dimen sional vector space over a finite field. The SSP lemma fails for some lat tices\, and we identify a local obstruction which we conjecture is the onl y reason for such failure.\n\nThe talk will not assume any familiarity wit h VC theory or with statistical learning theory.\n\nJoint work with Stijn Cambie (Raboud University Nijmegen)\, Bogdan Chornomaz (Vanderbilt Univers ity)\, Zeev Dvir (Princeton University) and Shay Moran (Technion).\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/16/ END:VEVENT BEGIN:VEVENT SUMMARY:Christoph Haase (UCL\, London) DTSTART:20201110T181500Z DTEND:20201110T184500Z DTSTAMP:20260404T111331Z 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\nAbstract\nGiven a finite set of $n \\times n$ integer matrices $\\math cal M$ that\ngenerate a finite multiplicative semigroup $\\overline{\\math cal M}$\, I am\ngoing to present a recent result showing that any $M \\in\ n\\overline{\\mathcal M}$ is a product of at most $2^{O(n^2 \\log n)}$\nel ements from $\\mathcal M$. This bound immediately implies a bound on\nthe cardinality of $\\overline{\\mathcal M}$.\n\nI will provide a non-technica l proof sketch demonstrating how the\naforementioned bound can be obtained . In addition\, I will discuss the\nhistory of this problem\, its motivati on\, which is rooted in automata\ntheory\, related results that have appea red over the last decades\, and\nopen challenges.\n\nThe talk is based on joint work with Georgina Bumpus\, Stefan Kiefer\,\nPaul-Ioan Stoienescu an d Jonathan Tanner from Oxford\, which appeared at\nICALP'20\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/17/ END:VEVENT BEGIN:VEVENT SUMMARY:Giovanni Paolini (AWS and Caltech) DTSTART:20201201T181500Z DTEND:20201201T184500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/18 DESCRIPTION:Title: How to collapse a simplicial complex: theory and practice\nby Giovanni Paolini (AWS and Caltech) as part of LA Combinatorics and Complex ity Seminar\n\n\nAbstract\nSometimes one wants to answer topological quest ions about a simplicial complex: Is it contractible? Does it deformation r etract onto a certain subcomplex? What is its homotopy type? What is its h omology? In this talk\, I will introduce discrete Morse theory\, which all ows approaching these questions in a purely combinatorial way\, by constru cting sequences of "elementary collapses" between pairs of simplices. Then I will outline algorithms and hardness results for collapsibility and dis crete Morse theory.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/18/ END:VEVENT BEGIN:VEVENT SUMMARY:Bhaskar DasGupta (UIC) DTSTART:20201208T181500Z DTEND:20201208T184500Z DTSTAMP:20260404T111331Z UID:LA-CoCo/19 DESCRIPTION:Title: Removing partisan bias in redistricting: computational complexity meets the science of gerrymandering\nby Bhaskar DasGupta (UIC) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nPartisan gerrym andering is a major cause for voter disenfranchisement in United States. H owever\, convincing US courts to adopt specific measures to quantify gerry mandering has been of limited success to date. Stephanopoulos and McGhee i n several papers introduced a new measure of partisan gerrymandering via t he so-called "efficiency gap" that computes the absolute difference of was ted votes between two political parties in a two-party system\; from a leg al point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisco nsin was gerrymandered. The goal of this talk is to formalize and provide theoretical and empirical algorithmic analyses of the computational proble m of minimizing this measure. To this effect\, we show the following:\n\n1 . On the theoretical side\, we formalize the corresponding minimization pr oblem and provide non-trivial mathematical and computational complexity pr operties of the problem of minimizing the efficiency gap measure. These ar e the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering.\n\n2. On the empirical side\, we provid e a simple and fast algorithm that can "un-gerrymander" the district maps for the states of Texas\, Virginia\, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable l evels from the current unacceptable levels. To the best of our knowledge\, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that\, notwithstanding the general worst-case approxi mation hardness of the efficiency gap measure as shown by us\, finding dis trict maps with acceptable levels of efficiency gaps could be a computatio nally tractable problem from a practical point of view. Based on these emp irical results\, we also provide some interesting insights into three prac tical issues related the efficiency gap measure.\n\nJoint work with Tanima Chatterjee\, Laura Palmieri\, Zainab Al-Qurashi and Anastasios Sidiropoul os.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/19/ END:VEVENT BEGIN:VEVENT SUMMARY:Dustin G. Mixon (OSU) DTSTART:20201208T190000Z DTEND:20201208T193000Z DTSTAMP:20260404T111331Z 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\nE very decade\, politicians update voting districts to account for populatio n shifts as measured by the U.S. Census. Of course\, partisan politicians are inclined to draw maps that favor their own party\, resulting in partis an gerrymandering. In this talk\, we will explore how tools from mathemati cs can help to deter this growing threat to democracy.\n\nOur main result is that deciding whether there exists a fair redistricting among legal map s is NP-hard. Joint work with Richard Kueng and Soledad Villar.\n LOCATION:https://stable.researchseminars.org/talk/LA-CoCo/20/ END:VEVENT END:VCALENDAR