BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1435
DTSTAMP:20240619T094028Z
SUMMARY:Tree evaluation in space O(log n . log log n)
DESCRIPTION:Speaker: Bikshan Chatterjee (TIFR)\n\nAbstract: \nTree Evaluati
 on was considered to be a candidate problem solvable in polynomial time bu
 t not in log space. The natural algorithm for performing tree evaluation t
 akes roughly log^2(n) space and was conjectured to be optimal. The belief 
 was based on an assumption that space being used for storing old values ca
 nnot be used for new computation. Cook and Mertz showed this assumption to
  be false\, in earlier work. In this paper\, they improve the space comple
 xity to O(log n . log log n) using similar strategy of reusing space being
  used for storing old values without erasing it.\n
URL:https://www.tcs.tifr.res.in/web/events/1435
DTSTART;TZID=Asia/Kolkata:20240621T140000
DTEND;TZID=Asia/Kolkata:20240621T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR