BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Amir Yehudayoff (Technion\, Haifa)
DTSTART;VALUE=DATE-TIME:20201006T163000Z
DTEND;VALUE=DATE-TIME:20201006T170000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201013T171500Z
DTEND;VALUE=DATE-TIME:20201013T174500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201013T163000Z
DTEND;VALUE=DATE-TIME:20201013T170000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201006T171500Z
DTEND;VALUE=DATE-TIME:20201006T174500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201020T163000Z
DTEND;VALUE=DATE-TIME:20201020T170000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201020T171500Z
DTEND;VALUE=DATE-TIME:20201020T174500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201027T163000Z
DTEND;VALUE=DATE-TIME:20201027T170000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201124T181500Z
DTEND;VALUE=DATE-TIME:20201124T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201110T173000Z
DTEND;VALUE=DATE-TIME:20201110T180000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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\n***Smale
'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;VALUE=DATE-TIME:20201117T173000Z
DTEND;VALUE=DATE-TIME:20201117T180000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201103T173000Z
DTEND;VALUE=DATE-TIME:20201103T180000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201117T181500Z
DTEND;VALUE=DATE-TIME:20201117T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201103T181500Z
DTEND;VALUE=DATE-TIME:20201103T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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\n*Shellabi
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;VALUE=DATE-TIME:20201201T173000Z
DTEND;VALUE=DATE-TIME:20201201T180000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201027T171500Z
DTEND;VALUE=DATE-TIME:20201027T174500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201124T173000Z
DTEND;VALUE=DATE-TIME:20201124T180000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201110T181500Z
DTEND;VALUE=DATE-TIME:20201110T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201201T181500Z
DTEND;VALUE=DATE-TIME:20201201T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201208T181500Z
DTEND;VALUE=DATE-TIME:20201208T184500Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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;VALUE=DATE-TIME:20201208T190000Z
DTEND;VALUE=DATE-TIME:20201208T193000Z
DTSTAMP;VALUE=DATE-TIME:20230202T142148Z
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