All reports by Author Pascal Koiran:

__
TR04-003
| 22nd December 2003
__

Pascal Koiran#### Valiant's model and the cost of computing integers

__
TR95-051
| 16th October 1995
__

Pascal Koiran#### VC Dimension in Circuit Complexity

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

Pascal Koiran

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