BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1703
DTSTAMP:20260326T091123Z
SUMMARY:Catalytic Graph Algorithms
DESCRIPTION:Speaker: Shubham Bhardwaj (TIFR)\n\nAbstract: \nCatalytic compu
 tation asks: how much does access to a full but reusable tape amplify our 
 computational power? In this talk\, we explore this question in the contex
 t of graph algorithms and logspace complexity.\nWe present three results: 
 NL ⊆ CL\, showing that nondeterministic logspace computations can be sim
 ulated catalytically\; BPL ⊆ CL\, showing the same for randomized logspa
 ce\; and the collapse CBPL = CNL = CL\, revealing that in the catalytic re
 gime\, nondeterminism and randomness likely afford no additional power ove
 r determinism — a striking contrast to the standard logspace world where
  such separations remain wide open.\nWe also discuss some key design princ
 iples that underpin catalytic algorithms.\n
URL:https://www.tcs.tifr.res.in/web/events/1703
DTSTART;TZID=Asia/Kolkata:20260327T160000
DTEND;TZID=Asia/Kolkata:20260327T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR