[Proof Complexity] CORRECTION: MIAO/BARC seminar Tue Apr 22 at 14:00 CET with Ian Mertz: Catalytic computing: A primer
Jakob Nordström
jn at di.ku.dk
Mon Apr 14 14:26:17 CEST 2025
My apologies --- as it says in the message proper, the day is TUESDAY
April 22 and nothing else, just to avoid any confusion... /Jakob
-------- Forwarded Message --------
Subject: MIAO/BARC seminar Thu Apr 22 at 14:00 CET with Ian Mertz:
Catalytic computing: A primer
Date: Mon, 14 Apr 2025 14:15:21 +0200
From: Jakob Nordström <jn at di.ku.dk>
To: MIAO theory seminar <miao-seminar-theory at cs.lth.se>
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
More information about the Proof-Complexity
mailing list