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 1$. It is ... more >>>

The main result of this paper is a Omega(n^{1/4}) lower bound on the size of a sigmoidal circuit computing a specific AC^0_2 function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the same function ... more >>>