Pascal Koiran

Let $\tau(k)$ be the minimum number of arithmetic operations

required to build the integer $k \in \N$ from the constant 1.

A sequence $x_k$ is said to be ``easy to compute'' if

there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$

for all $k \geq ...
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 >>>