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