Computing with a full memory

Add to your list(s) Download to your calendar using vCal

• Florian Speelman (CWI)
• Thursday 30 January 2014, 14:15-15:15
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact William Matthews.

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform TC1 -circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. TC1 -circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace. In order to obtain our results we study an algebraic model of computation, extending the framework and techniques of Ben-Or and Cleve (1992).

Joint work with Harry Buhrman, Richard Cleve, Michal Koucký and Bruno Loff.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.