BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Computing with a full memory - Florian Speelman (CWI)
DTSTART:20140130T141500Z
DTEND:20140130T151500Z
UID:TALK50401@talks.cam.ac.uk
CONTACT:William Matthews
DESCRIPTION:We define the notion of a _catalytic-space computation_. This 
 is a computation that has a\nsmall amount of clean space available and is 
 equipped with additional auxiliary space\, with the\ncaveat that the addit
 ional space is initially in an arbitrary\, possibly incompressible\, state
  and\nmust be returned to this state when the computation is finished. We 
 show that the extra space\ncan be used in a nontrivial way\, to compute un
 iform TC1-circuits with just a logarithmic amount\nof clean space. The ext
 ra space thus works analogously to a catalyst in a chemical reaction.\nTC1
 -circuits can compute for example the determinant of a matrix\, which is n
 ot known to be\ncomputable in logspace. In order to obtain our results we 
 study an algebraic model of computation\, extending the framework and tech
 niques of Ben-Or and Cleve (1992).\n\nJoint work with Harry Buhrman\, Rich
 ard Cleve\, Michal Koucký and Bruno Loff.
LOCATION:MR4\,  Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR