[Proof Complexity] MIAO/BARC seminar Thu Apr 22 at 14:00 CET with Ian Mertz: Catalytic computing: A primer

[Jakob Nordström]

Dear all,

On Tuesday next week at 14:00 CET we will have the pleasure of welcoming 
Ian Mertz from Charles University, who will present a seminar titled 
"Catalytic computing: A primer". You find the abstract at the bottom of 
this message.

We will run this as a MIAO/BARC hybrid seminar at the University of 
Copenhagen. Local participants are warmly welcome to seminar room N116 
at Universitetsparken 1, while other participants are equally warmly 
welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . 
Please feel free to share this information with colleagues who you think 
might be interested. We are also hoping to record the seminar and post 
on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch 
for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********
/
Tuesday Apr 22 at 14:00 in seminar room N116, Universitetsparken 1, 
University of Copenhagen, and on Zoom
*Catalytic computing: A primer
*(Ian Mertz, Charles University)/

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.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se