BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1004
DTSTAMP:20230914T125946Z
SUMMARY:Shortest Paths and Newton Polytopes
DESCRIPTION:Speaker: Kshitij Gajjar (IIIT Delhi) and Prerona Chatterjee (ST
CS\, TIFR)\n\nAbstract: \nAbstract: In this talk\, we will explore a surpr
ising connection between graph theory and convex geometry. We look at grap
hs whose edge weights are linear forms in $d$ variables. That is\, the wei
ght of each edge $e$ is given by $w_e (\\lambda_1\, \\lambda_2\, \\ldots\,
\\lambda_d) = a_{e\,1} \\lambda_1 + a_{e\,2} \\lambda_2 + \\cdots + a_{e\
,d} \\lambda_d$.\nIn the first part of this talk\, Kshitij will show how t
he different shortest paths in such a graph (for different values of $\\la
mbda_1\, \\lambda_2\, \\ldots\, \\lambda_d$) can be thought of as the extr
eme points of a polytope in $d$ dimensions.\nIn the second part of this ta
lk\, Prerona will explain how to upper bound the number of extreme points
in such polytopes. If time permits\, she will show that improving this res
ult can help solve some questions in algebraic circuit complexity.\nThis i
s based on joint work with Jaikumar Radhakrishnan and Vaishali Surianaraya
nan.\n
URL:https://www.tcs.tifr.res.in/web/events/1004
DTSTART;TZID=Asia/Kolkata:20191011T171500
DTEND;TZID=Asia/Kolkata:20191011T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR