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 >>>

Aggregates are a computational model similar to circuits, but the
underlying graph is not necessarily acyclic. Logspace-uniform
polynomial-size aggregates decide exactly the languages in PSPACE;
without uniformity condition they decide the languages in
PSPACE/poly. As a measure of similarity to boolean circuits we
introduce the parameter component size. We ... more >>>