![]() |
COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. | ![]() |
Computing with a full memoryAdd 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. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsCambridge University Engineering Department Talks Outreach CMS Special LecturesOther talksThe persistence and transience of memory Visual Analytics for High-Dimensional Data Exploration and Engineering Design Machine learning, social learning and self-driving cars The role of Birkeland currents in the Dungey cycle THE PYE STORY Wetting and elasticity: 2 experimental illustrations |