Campus Event Calendar
Event Entry
What and Who
Catalytic Computing: A Primer
Ian Mertz
Charles University, Prague
AG1 Advanced Mini-Course
Postdoctoral researcher
Computer Science Institute (IUUK)
Faculty of Mathematics and Physics
Charles University
Homepage: https://iuuk.mff.cuni.cz/~iwmertz/
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 18 February 2025
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Can memory be useful even when it's already full? In the catalytic computing model (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 initial 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 field of catalytic computation. We will cover the base catalytic model and where 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-or-random approaches; applications of catalytic ideas to other settings; and potential directions for the future of the field.
In this talk we will survey the field of catalytic computation. We will cover the base catalytic model and where 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-or-random approaches; applications of catalytic ideas to other settings; and potential directions for the future of the field.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 02/17/2025 12:31 -- Created document.