Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

We consider strings which are succinctly described. The description

is in terms of straight-line programs in which the constants are

symbols and the only operation is the concatenation. Such

descriptions correspond to the systems of recurrences or to

context-free grammars generating single words. The descriptive ...
more >>>

Matthias Galota, Heribert Vollmer

We show that the class of integer-valued functions computable by

polynomial-space Turing machines is exactly the class of functions f

for which there is a nondeterministic polynomial-time Turing

machine with a certain order on its paths that on input x outputs a 3x3

matrix with entries from {-1,0,1} on each ...
more >>>

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

We study two quite different approaches to understanding the complexity

of fundamental problems in numerical analysis. We show that both hinge

on the question of understanding the complexity of the following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>