on 05-05-2014
ICT2014 - 5-7 May 2014, Lisbon, Portugal
TELECOMMUNICATIONS: COOPERATION FOR A UNITED WORLD
ICT 2014 will feature world-class plenary speakers, tutorials and technical sessions from academia, researching laboratories, government, industry(operators and suppliers) and security public services to discuss and exchange ideas in the fields of wireless and cable telecommunication networks, services and applications. The conference will also include an expo program and exhibition.
Important dates
Paper submission deadline: December 2nd, 2013
Notification of acceptance: February 17th, 2014
Final paper due: March 10th, 2014
Special session proposals: October 14th, 2013
Workshop proposals: October 14th, 2013
Tutorial proposals: October 14th, 2013
Plenary talks: October 14th, 2013
Exhibit proposals: December 17th, 2013
More Information..
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.
More Information..