BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/697
DTSTAMP:20230914T125934Z
SUMMARY:Subcubic Equivalences Between Matrix\, Path and Triangle Problems
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nIn this talk\, we will di
 scuss subcubic equivalence between the following problems:\n\n- Finding th
 e distance product of matrices\n- Directed all pairs shortest paths\n- Und
 irected all pairs shortest paths\n- Replacement paths\n- Second shortest s
 imple path\n- Detecting a triangle with negative total weight\n\nAll the a
 bove mentioned problems have cubic time algorithm\, but neither a cubic lo
 wer bound nor a subcubic time algorithm is known for any of them. The equi
 valence shows that either all or none of them have a subcubic algorithm.\n
 \nThese equivalences appear as a part of the 2010 FOCS paper by Virginia W
 illiams and Ryan Williams.\n\nWe will begin by formalizing the notion of s
 ubcubic equivalence and the distance product of matrices.\n\nNote: These a
 re the equivalences that were not covered during the qualifiers. But we wi
 ll be covering the required basics again.\n\n\n \n
URL:https://www.tcs.tifr.res.in/web/events/697
DTSTART;TZID=Asia/Kolkata:20160715T160000
DTEND;TZID=Asia/Kolkata:20160715T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR