BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Computing with a full memory - Florian Speelman (C
WI)
DTSTART;TZID=Europe/London:20140130T141500
DTEND;TZID=Europe/London:20140130T151500
UID:TALK50401AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/50401
DESCRIPTION:We define the notion of a _catalytic-space computa
tion_. This is a computation that has a\nsmall amo
unt of clean space available and is equipped with
additional auxiliary space\, with the\ncaveat that
the additional space is initially in an arbitrary
\, possibly incompressible\, state and\nmust be re
turned to this state when the computation is finis
hed. We show that the extra space\ncan be used in
a nontrivial way\, to compute uniform TC1-circuits
with just a logarithmic amount\nof clean space. T
he extra space thus works analogously to a catalys
t in a chemical reaction.\nTC1-circuits can comput
e for example the determinant of a matrix\, which
is not known to be\ncomputable in logspace. In ord
er to obtain our results we study an algebraic mod
el of computation\, extending the framework and te
chniques of Ben-Or and Cleve (1992).\n\nJoint work
with Harry Buhrman\, Richard Cleve\, Michal Kouck
ý and Bruno Loff.
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:William Matthews
END:VEVENT
END:VCALENDAR