BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se iCalcreator 2.41.90//
CALSCALE:GREGORIAN
UID:39383437-3432-4030-b833-333235613962
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:35316638-6638-4735-b365-646536396261
DTSTAMP:20240725T193933Z
CREATED:20240212T154359Z
DESCRIPTION:Topic: Lower Bounds for Set-Multilinear Branching Programs\n\nS
peakers: Shubhangi Saraf\n\nIn this talk\, I will discuss lower bounds for
a certain\nset-multilinear restriction of algebraic branching programs. T
he\nsignificance of the lower bound and the model is underscored by the\nr
ecent work of Bhargav\, Dwivedi\, and Saxena (2023)\, which showed that\ns
uper-polynomial lower bounds for the model of sum of ordered set\nmultilin
ear ABPs -- when the underlying polynomial of sufficiently low\ndegree --
would imply super-polynomial lower bounds against general\nABPs\, thereby
resolving Valiant's longstanding conjecture that the\npermanent polynomial
cannot be computed efficiently by ABPs. We will\ndiscuss a recent result
which 'almost' meets this low-degree demand.\n\nThis is based on joint wor
k with Prerona Chatterjee\, Deepanshu Kush\nand Amir Shpilka.
DTSTART:20240429T150000Z
DTEND:20240429T160000Z
LAST-MODIFIED:20240502T191719Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-570
END:VEVENT
BEGIN:VEVENT
UID:65316138-3333-4162-b436-623235383664
DTSTAMP:20240725T193933Z
CREATED:20240314T154957Z
DESCRIPTION:Topic: Incidence Bounds via Extremal Graph Theory\n\nSpeakers:
Istvan Tomon\n\nA cornerstone result in geometry is the Szemerédi–Trotter
theorem\,\nwhich gives a sharp bound on the maximum number of incidences b
etween\n$m$ points and $n$ lines in the real plane. A natural generalizati
on\nof this is to consider point-hyperplane incidences in higher\ndimensio
ns. As proposed by Chazelle in the 90's\, we are interested in\nthe maximu
m number of incidences between $m$ points and $n$\nhyperplanes\, assuming
no $s$ points lie in the intersection of $s$\nhyperplanes. The latter cond
ition is needed to\navoid trivialities\, like all hyperplanes intersecting
in a\nline\, and all points contained in this line. Starting from dimensi
on\n3\, matching lower and upper bounds are no longer known for this\nprob
lem. I will talk about how to prove sharp bounds over arbitrary\nfields us
ing methods from extremal graph theory\, and discuss\nanalogues of this pr
oblem concerning point-variety incidences and\nunit distance graphs.\n\nBa
sed on a joint work with Aleksa Milojević and Benny Sudakov.
DTSTART:20240430T143000Z
DTEND:20240430T163000Z
LAST-MODIFIED:20240502T191655Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-565
END:VEVENT
BEGIN:VEVENT
UID:66623936-6565-4136-b934-333530353763
DTSTAMP:20240725T193933Z
CREATED:20240503T120248Z
DESCRIPTION:Topic: Rounding Large Independent Sets on Expanders\n\nSpeakers
: Tim Hsieh\n\nIn this talk\, we will present a new approach for approxima
ting large\nindependent sets when the input graph is a one-sided expander—
that\nis\, the uniform random walk matrix of the graph has second eigenval
ue\nbounded away from 1. Specifically\, we show a polynomial time algorith
m\nthat can find linear-sized independent sets in one-sided expanders\ntha
t are almost $3$-colorable or promised to contain a $0.499n$-sized\nindepe
ndent set.\n\nAll prior algorithms that beat the worst-case guarantees for
the\nproblem rely on bottom eigenspace enumeration techniques\, which bui
ld\non a classical work of Alon and Kahale and require two-sided expansion
\n(i.e.\, bounded number of negative eigenvalues of magnitude close to\n1)
. Such techniques provably fail in our setting because in contrast\nto bot
tom eigenspace enumeration that naturally extends to\n$k$-colorable graphs
for any fixed constant $k$\, we observe that\nfinding linear-sized indepe
ndent sets in almost $4$-colorable\nexpanding graphs (as opposed to almost
$3$-colorable graphs in our\nalgorithmic result above) is NP-hard assumin
g the Unique Games\nConjecture.\n\nOur algorithms rely on a new framework
for rounding sum-of-squares\nrelaxations of the independent set problem ba
sed on a combinatorial\napproximate packing property—in any graph that sat
isfies one-sided\nspectral expansion (in fact\, a weaker vertex expansion
property\nsuffices)\, the total number of large independent sets with smal
l\npairwise intersections is small.\n\nBased on joint work with Mitali Baf
na and Pravesh K. Kothari.
DTSTART:20240506T150000Z
DTEND:20240506T160000Z
LAST-MODIFIED:20240507T175221Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-574
END:VEVENT
BEGIN:VEVENT
UID:63623562-3335-4265-b334-383865633235
DTSTAMP:20240725T193933Z
CREATED:20240329T180207Z
DESCRIPTION:Topic: Quantum Mechanics\, Semidefinite Programming\, and Graph
Invariants\n\nSpeakers: Matthew Hastings\n\nThe central problem of physic
s and quantum chemistry is to find the\nground state energy of some physic
al system governed by quantum\nmechanics. In mathematical terms\, this me
ans finding the lowest\neigenvalue of some linear operator on a vector spa
ce with a tensor\nproduct structure. Since the dimension of the vector sp
ace grows\nexponentially with the size of the physical system\, the proble
m\nquickly becomes computationally intractable. Semidefinite\nprogramming
methods are one interesting way of approximating the\nsolution. Even the
se methods can become computationally difficult as\nthe order of the semid
efinite program increases\, but low order methods\ncan provide useful info
rmation. I will review some of these methods\,\nand give some positive an
d negative results showing their power and\nlimitations on various physica
l systems. Finally\, I will explain an\ninteresting new graph invariant s
uggested by these methods and give\nsome preliminary results on that invar
iant.
DTSTART:20240513T150000Z
DTEND:20240513T160000Z
LAST-MODIFIED:20240513T124559Z
LOCATION:Simonyi 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-573
END:VEVENT
BEGIN:VEVENT
UID:62643237-3065-4066-b365-386633343137
DTSTAMP:20240725T193933Z
CREATED:20240508T154919Z
DESCRIPTION:Topic: Resolution of the Kohayakawa--Kreuter Conjecture \n\nSpe
akers: Raphael Steiner\n\nA graph $G$ is said to be Ramsey for a tuple of
graphs ($H_1\,...\,H_r$)\nif every $r$-coloring of the edges of $G$ contai
ns a monochromatic\ncopy of $H_i$ in color $i$\, for some $i$. A fundament
al question at\nthe intersection of Ramsey theory and the theory of random
graphs is\nto determine the threshold at which the binomial random graph
\n$G_{n\,p}$ becomes a.a.s. Ramsey for a fixed tuple ($H_1\,...\,H_r$)\, a
nd\na famous conjecture of Kohayakawa and Kreuter predicts this threshold.
\nEarlier work of Mousset-Nenadov-Samotij\, Bowtell-Hancock-Hyde\, and\nKu
perwasser-Samotij-Wigderson has reduced this probabilistic problem\nto a d
eterministic graph decomposition conjecture.\n\nIn this talk\, I will disc
uss history and background of this problem\nand sketch our recent proof (j
oint with M. Christoph\, A. Martinsson\,\nY. Wigderson) that the determini
stic graph decomposition conjecture is\ntrue\, thus resolving the Kohayaka
wa-Kreuter conjecture.
DTSTART:20240514T143000Z
DTEND:20240514T163000Z
LAST-MODIFIED:20240514T182810Z
LOCATION:Simonyi Hall 101 and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-566
END:VEVENT
END:VCALENDAR