BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1643
DTSTAMP:20251126T054942Z
SUMMARY:Catalytic Computing: A Primer
DESCRIPTION:Speaker: Ian Mertz (Charles University)\n\nAbstract: \nCan memo
 ry be useful even when it's already full? In the catalytic computing mode
 l (Buhrman et al. 2014)\, we consider a space bounded Turing machine with 
 additional access to a much larger hard drive\, with the caveat that the i
 nitial contents of this extra space must be restored after any computation
 . Despite this restriction\, catalytic computation gains surprising power
  over ordinary space-bounded computation\, even above and beyond resources
  such as randomness and non-determinism.In this talk we will survey the fi
 eld of catalytic computation. We will cover the base catalytic model and w
 here it fits into traditional complexity theory\; variants of the model\, 
 such as lossy\, randomized\, non-deterministic\, and non-uniform catalytic
  computation\; known techniques\, such as register programs and compress-o
 r-random approaches\; applications of catalytic ideas to other settings\; 
 and potential directions for the future of the field.\nShort Bio:Ian Mertz
  is a postdoctoral researcher at the Computer Science Institute (IUUK) at 
 Charles University in Prague. His work revolves around catalytic computing
 \, a branch of space-bounded algorithms dealing with the use of full memor
 y as a computational resource\, as well as the study of how the complexity
  of problems compose over many instances. He received a B.Sc./B.A. from Ru
 tgers University in 2016\, an M.Sc. from University of Toronto in 2018\, a
 nd a Ph.D. in computer science from University of Toronto in 2022\, and ha
 s since held positions at University of Warwick and Charles University.\n
URL:https://www.tcs.tifr.res.in/web/events/1643
DTSTART;TZID=Asia/Kolkata:20251128T113000
DTEND;TZID=Asia/Kolkata:20251128T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR