University of Cambridge > Talks.cam > CQIF Seminar > Computing with a full memory

Computing with a full memory

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity