on 24-04-2014
B. Loff
April 24, 2014, Friday, 16h15m.
Abstract: 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, a variant of straight-line programs. We employ register machines with input registers x_1,…,x_n and work registers r_1,…,r_m. The instructions available are of the form r_i <- r_i +- u * v, with r_i a register and, u,v distinct registers or constants. We wish to compute a function f(x_1,…,x_n) through a sequence of such instructions. The working registers have some arbitrary initial value r_i=\tau_i, and they may be altered throughout the computation, but by the end all registers must be returned to their initial value \tau_i, except for, say, r_1 which must hold \tau_1+f(x_1,…,x_n). We show that all of Valiant’s class VP, and more, can be computed in this model. This significantly extends the framework and techniques of Ben-Or and Cleve [1]. This is joint work with Harry Buhrman, Richard Cleve, Michal Koucký and Florian Speelman. [1] M. Ben-Or and R. Cleve. Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing, 21(1):54–58, 1992.
Room: 3.10, Mathematics
Support: SQIG/Instituto de Telecomunicações with support from FCT and FEDER namely by the FCT project PEst-OE/EEI/LA0008/2013.