BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//85f20b73fecb3e0e6ca434791a2aea4a.ias.edu//NONSGML kigkonsult.se iCalcreator 2.41.64//
CALSCALE:GREGORIAN
UID:65633764-3335-4234-a363-646461623431
X-WR-TIMEZONE:UTC
X-WR-CALNAME:IAS CSDM Seminars
BEGIN:VEVENT
UID:66386261-6439-4237-b966-326131663064
DTSTAMP:20220929T213812Z
CREATED:20220719T140656Z
DESCRIPTION:Topic: Graphs as geometric objects\n\nSpeakers: Nathan Linial\n
\nAffiliation: The Hebrew University\n\nIt may seem quite obvious that gra
phs carry a lot of geometric\nstructure. Don't we learn in algorithm clas
ses how to solve\nall-pairs-shortest-paths\, minimum spanning trees etc.?
However\, in\nthis talk\, I will try to impress on you the idea that ther
e is much\nmore to be discovered here. For example: Let G=(V\,E) be a gra
ph and\nlet w be a mapping from E to the positive reals. Let us restrict
\nourselves to the case where no ties occur and so for every two\ndistinct
vertices u\,v there is a unique w-shortest path that connects\nthem (uniq
ueness holds with probability 1). Let w’ be another set\nof positive weig
hts on E. We consider w and w’ equivalent if they\ndefine the same system
of shortest paths. Question: Given a graph G\nhow many such different eq
uivalence classes can it have at least/at\nmost? Also\, we say that a path
system on G is consistent if it is\nclosed under taking subpaths. Questi
on: Does every consistent path\nsystem on G come from a function w as abov
e? The answer is an\nemphatic NO. \n\nThe new results are from joint work
with my student Daniel Cizma.
DTSTART:20220725T151500Z
DTEND:20220725T161500Z
LAST-MODIFIED:20220725T171053Z
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-512
END:VEVENT
BEGIN:VEVENT
UID:64363466-6338-4339-a366-353434643739
DTSTAMP:20220929T213812Z
CREATED:20220808T182859Z
DESCRIPTION:Topic: Making Proofs More Constructive\, and Algorithms Less Ra
ndom\n\nSpeakers: Oliver Korten\n\nAffiliation: Columbia University\n\nA c
entral topic in the theory of computation is\n_derandomization:_ say we ha
ve an algorithm which flips coins to\nachieve some goal\, and succeeds wit
h high probability. Can we\ntransform this algorithm into a deterministic
procedure\, while\nmaintaining most of its desirable behavior (i.e. effici
ency and\ncorrectness)? \n\nA similar (though more informal) question aris
es frequently in\ncombinatorics: say we have a non-constructive proof of t
he existence\nof some object. Can we replace this proof with a more\n“cons
tructive” argument\, without weakening the result too much?\n\nIn this wor
k we will show some formal connections between these two\nsorts of questio
ns\, using the framework of “total search\nproblems.” This framework will
allow us to establish new relations\namongst outstanding complexity-theore
tic problems pertaining to\nboolean circuit-size lower bounds\, time-space
tradeoffs for turing\nmachines\, and deterministic constructions of vario
us combinatorial\nobjects.
DTSTART:20220926T151500Z
DTEND:20220926T161500Z
LAST-MODIFIED:20220926T123922Z
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-514
END:VEVENT
BEGIN:VEVENT
UID:63303434-3035-4666-a634-666561366566
DTSTAMP:20220929T213812Z
CREATED:20220808T191625Z
DESCRIPTION:Topic: Robust sublinear expanders\, and an application towards
the Erdos-Gallai conjecture\n\nSpeakers: Matija Bucic\n\nAffiliation: Vebl
en Research Instructor\, School of Mathematics\n\nExpander graphs have bee
n perhaps one of the most widely useful\nclasses of graphs ever considered
. In this talk we will focus on a\nfairly weak notion of expanders called
sublinear expanders\, first\nintroduced by Komlos and Szemeredi around 25
years ago. They have\nfound many remarkable applications ever since. In pa
rticular we will\nfocus on certain robustness conditions one may impose on
sublinear\nexpanders while still maintaining their most useful property\,
the fact\nthat in any graph one can find a sublinear expander subgraph of
almost\nthe same density. We will discuss a number of useful properties o
f\nsuch robust sublinear expanders and show how they come together to\nbri
ng us only a $\log^{\star}$ factor away from proving one of the\nmost clas
sical decomposition conjectures\, the Erdos-Gallai cycle\ndecomposition co
njecture.\n\nBased on joint work with Richard Montgomery.
DTSTART:20220927T143000Z
DTEND:20220927T163000Z
LAST-MODIFIED:20220927T130400Z
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-512
END:VEVENT
BEGIN:VEVENT
UID:39353166-3630-4636-b137-376238353062
DTSTAMP:20220929T213812Z
CREATED:20220808T182924Z
DESCRIPTION:Topic: Relative rank and regularity\n\nSpeakers: Tamar Ziegler
\n\nAffiliation: Hebrew University\; Distinguished Visiting Professor\, Sc
hool of Mathematics\n\nThe notion of Schmidt rank/strength for a collectio
n of m polynomials\nplays an important role in additive combinatorics\, nu
mber theory and\ncommutative algebra\; high rank collections of polynomial
s are\n“psuedorandom”. An arbitrary collection of polynomials is not\nnec
essarily of high rank\, but via a regularity procedure is contained\nin an
ideal generated by a huge (depending on m) high rank collection\nof polyn
omials. We describe a refined notion of rank/strength that\nallows for a n
ew regularization procedure with polynomial dependence\non m\, while maint
aining the psuedorandomess properties.\n\nJoint work with A. Lampert.\n\n
DTSTART:20221003T151500Z
DTEND:20221003T161500Z
LAST-MODIFIED:20220922T123417Z
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-515
END:VEVENT
BEGIN:VEVENT
UID:38303132-6636-4639-a531-626637333533
DTSTAMP:20220929T213812Z
CREATED:20220808T191647Z
DESCRIPTION:Topic: Almost Ramanujan Expanders from Arbitrary Expanders via
Operator Amplification\n\nSpeakers: Fernando Granha Jeronimo\n\nAffiliatio
n: Member\, School of Mathematics\n\nExpander graphs are fundamental objec
ts in theoretical computer\nscience and mathematics. They have numerous ap
plications in diverse\nfields such as algorithm design\, complexity theory
\, coding theory\,\npseudorandomness\, group theory\, etc.\n\nIn this talk
\, we will describe an efficient algorithm that transforms\nany bounded de
gree expander graph into another that achieves almost\noptimal (namely\, n
ear-quadratic\, $d \leq 1/\lambda^{2+o(1)}$)\ntrade-off between (any desir
ed) spectral expansion $\lambda$ and\ndegree $d$. The optimal quadratic tr
ade-off is known as the Ramanujan\nbound\, so our construction gives almos
t Ramanujan expanders from\narbitrary expanders.\n\nThis transformation pr
eserves structural properties of the original\ngraph\, and thus has many c
onsequences. Applied to Cayley graphs\, our\ntransformation shows that any
expanding finite group has almost\nRamanujan expanding generators. Simila
rly\, one can obtain almost\noptimal explicit constructions of quantum exp
anders\, dimension\nexpanders\, monotone expanders\, etc.\, from existing
(suboptimal)\nconstructions of such objects.\n\nOur results generalize Ta-
Shma's technique in his breakthrough paper\n[STOC 2017] used to obtain exp
licit almost optimal binary codes.\nSpecifically\, our spectral amplificat
ion extends Ta-Shma's analysis of\nbias amplification from scalars to matr
ices of arbitrary dimension in\na very natural way.\n\nJoint work with: Tu
shant Mittal\, Sourya Roy and Avi Wigderson
DTSTART:20221004T143000Z
DTEND:20221004T163000Z
LAST-MODIFIED:20220928T151011Z
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-513
END:VEVENT
BEGIN:VEVENT
UID:39623138-3337-4161-b534-626133396432
DTSTAMP:20220929T213812Z
CREATED:20220808T182957Z
DESCRIPTION:Topic: Is your distribution in shape? \n\nSpeakers: Ronitt Rub
infeld\n\nAffiliation: Massachusetts Institute of Technology\n\nAlgorithms
for understanding data generated from distributions over\nlarge discrete
domains are of fundamental importance. In this talk\,\nwe consider the sa
mple complexity of *property testing algorithms*\nthat seek to to distingu
ish whether or not an underlying distribution\nsatisfies basic shape prope
rties. Examples of such properties\ninclude convexity\, log-concavity\,
heavy-tailed\, and approximability by\nk-histogram functions. In this tal
k\, we will focus on the property\nof *monotonicity*\, as tools developed
for distinguishing the\nmonotonicity property have proven to be useful for
the all of the\nabove properties as well as several others. We say a dis
tribution p\nis 'monotone' if for any two comparable elements x0$ may be arbitrarily small\, and is secure\nagains
t adversaries running in exponential time $2^{O(n)}$. (A common\nconjectur
e is that there doesn't exist a verifier with such running\ntime that is s
ecure against all-powerful adversaries.)\n\nThe talk is based on a joint w
ork with Lijie Chen.
DTSTART:20221011T143000Z
DTEND:20221011T163000Z
LAST-MODIFIED:20220928T170827Z
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-514
END:VEVENT
BEGIN:VEVENT
UID:31346631-6561-4666-b733-343837303835
DTSTAMP:20220929T213812Z
CREATED:20220808T183028Z
DESCRIPTION:Topic: The Optimal Error Resilience of Interactive Communicatio
n over the Binary Alphabet\n\nSpeakers: Rachel Zhang\n\nAffiliation: Massa
chusetts Institute of Technology\n\nIn interactive coding\, Alice and Bob
wish to compute some function f\nof their private inputs x and y. They do
this by engaging in a\nnon-adaptive (fixed speaking order\, fixed length)
protocol to jointly\ncompute f(x\,y). The goal is to do this in an error-r
esilient way\, such\nthat even if some fraction of the communication is ad
versarially\ncorrupted\, both parties still learn f(x\,y). \n\nWe consider
an adversary who can cause errors\, meaning that\ncommunicated bits can b
e flipped adversarially\, and study the optimal\nerror resilience of such
a protocol. While the optimal error\nresilience over large alphabets is we
ll understood\, the situation over\nthe binary alphabet has remained open.
Prior to our works\, the best\nknown construction achieved resilience to
a 5/39 fraction of errors\,\nwhile the tightest upper bound was 1/6. The e
xact value of the optimal\nerror resilience attainable was still unknown.
In this talk\, I will\ndiscuss a new protocol that achieves the optimal er
ror resilience of\n1/6. This protocol has the following additional desirab
le properties:\nthe total communication is only a constant multiplicative
factor\nlarger than the communication of the noiseless protocol\, and the
\ncomputation time of Alice and Bob to simulate the noiseless transcript\n
is linear (up to log factors) in the communication of the noiseless\nproto
col.\n\nBased on joint work with Meghal Gupta.
DTSTART:20221017T151500Z
DTEND:20221017T161500Z
LAST-MODIFIED:20220929T114654Z
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-517
END:VEVENT
BEGIN:VEVENT
UID:62363537-3339-4964-a636-663030646465
DTSTAMP:20220929T213812Z
CREATED:20220808T191733Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Sushant Sachdeva\n\nAffiliation: Univer
sity of Toronto
DTSTART:20221018T143000Z
DTEND:20221018T163000Z
LAST-MODIFIED:20220923T200251Z
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-515
END:VEVENT
BEGIN:VEVENT
UID:65376639-3336-4262-a533-346132393033
DTSTAMP:20220929T213812Z
CREATED:20220808T183051Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Alex Wein\n\nAffiliation: New York Univ
ersity\n\n \n\n
DTSTART:20221024T151500Z
DTEND:20221024T161500Z
LAST-MODIFIED:20220823T010052Z
LOCATION:West Lecture Hall and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar I
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-i-518
END:VEVENT
BEGIN:VEVENT
UID:36646563-6232-4836-b164-346365393763
DTSTAMP:20220929T213812Z
CREATED:20220808T191800Z
DESCRIPTION:Topic: TBD
DTSTART:20221025T143000Z
DTEND:20221025T163000Z
LAST-MODIFIED:20220808T194307Z
LOCATION:West Lecture Hall and Remote Access
SUMMARY:Computer Science/Discrete Mathematics Seminar II
URL:https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-se
minar-ii-516
END:VEVENT
BEGIN:VEVENT
UID:65396631-6639-4561-a138-343465306464
DTSTAMP:20220929T213812Z
CREATED:20220808T183140Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Xi Chen\n\nAffiliation: Columbia Univer
sity\n\n \n\n
DTSTART:20221107T161500Z
DTEND:20221107T171500Z
LAST-MODIFIED:20220823T010200Z
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-520
END:VEVENT
BEGIN:VEVENT
UID:66336435-6662-4336-b932-636638353839
DTSTAMP:20220929T213812Z
CREATED:20220808T191852Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Leonardo Coregliano\n\nAffiliation: Mem
ber\, School of Mathematics
DTSTART:20221108T153000Z
DTEND:20221108T173000Z
LAST-MODIFIED:20220906T124435Z
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-518
END:VEVENT
BEGIN:VEVENT
UID:61626633-3539-4938-b731-633464613430
DTSTAMP:20220929T213812Z
CREATED:20220808T183211Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Yuval Efron\n\nAffiliation: Columbia Un
iversity\n\n \n\n
DTSTART:20221114T161500Z
DTEND:20221114T171500Z
LAST-MODIFIED:20220823T175120Z
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-521
END:VEVENT
BEGIN:VEVENT
UID:61343336-3536-4564-b532-623662663133
DTSTAMP:20220929T213812Z
CREATED:20220808T191912Z
DESCRIPTION:Topic: TBD
DTSTART:20221115T153000Z
DTEND:20221115T173000Z
LAST-MODIFIED:20220808T191926Z
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-519
END:VEVENT
BEGIN:VEVENT
UID:62316232-3030-4234-b138-653364373232
DTSTAMP:20220929T213812Z
CREATED:20220808T183247Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Huacheng Yu\n\nAffiliation: Princeton U
niversity\n\n \n\n
DTSTART:20221121T161500Z
DTEND:20221121T171500Z
LAST-MODIFIED:20220823T175239Z
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-522
END:VEVENT
BEGIN:VEVENT
UID:65376664-3331-4234-a330-376262303563
DTSTAMP:20220929T213812Z
CREATED:20220808T191942Z
DESCRIPTION:Topic: TBD
DTSTART:20221122T153000Z
DTEND:20221122T173000Z
LAST-MODIFIED:20220808T192001Z
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-520
END:VEVENT
BEGIN:VEVENT
UID:34303964-6336-4333-b462-623933393064
DTSTAMP:20220929T213812Z
CREATED:20220808T184429Z
DESCRIPTION:Topic: TBD\n\n \n\n
DTSTART:20221128T161500Z
DTEND:20221128T171500Z
LAST-MODIFIED:20220808T184444Z
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-523
END:VEVENT
BEGIN:VEVENT
UID:33636135-6439-4138-a633-643062613432
DTSTAMP:20220929T213812Z
CREATED:20220808T192011Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Mark Sellke\n\nAffiliation: Member\, Sc
hool of Mathematics
DTSTART:20221129T153000Z
DTEND:20221129T173000Z
LAST-MODIFIED:20220906T174955Z
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-521
END:VEVENT
BEGIN:VEVENT
UID:35313363-3939-4637-b566-323135303430
DTSTAMP:20220929T213812Z
CREATED:20220808T184501Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Kasper Green Larsen\n\nAffiliation: Aar
hus University \n\n \n\n
DTSTART:20221205T161500Z
DTEND:20221205T171500Z
LAST-MODIFIED:20220823T175444Z
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-524
END:VEVENT
BEGIN:VEVENT
UID:63353533-3431-4635-a463-626461613533
DTSTAMP:20220929T213812Z
CREATED:20220808T192039Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Nicole Wein\n\nAffiliation: Rutgers Uni
versity
DTSTART:20221206T153000Z
DTEND:20221206T173000Z
LAST-MODIFIED:20220823T175547Z
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-522
END:VEVENT
BEGIN:VEVENT
UID:32666230-3536-4361-b538-323832353535
DTSTAMP:20220929T213812Z
CREATED:20220808T184552Z
DESCRIPTION:Topic: TBD\n\nSpeakers: Mark Braverman\n\nAffiliation: Princeto
n University\n\n \n\n
DTSTART:20221212T161500Z
DTEND:20221212T171500Z
LAST-MODIFIED:20220906T124659Z
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-525
END:VEVENT
BEGIN:VEVENT
UID:35326565-3335-4133-b065-373731616639
DTSTAMP:20220929T213812Z
CREATED:20220808T192106Z
DESCRIPTION:Topic: TBD
DTSTART:20221213T153000Z
DTEND:20221213T173000Z
LAST-MODIFIED:20220808T192121Z
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-523
END:VEVENT
END:VCALENDAR