Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pascal Koiran:

TR04-003 | 22nd December 2003
Pascal Koiran

Valiant's model and the cost of computing integers

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

TR95-051 | 16th October 1995
Pascal Koiran

VC Dimension in Circuit Complexity

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

ISSN 1433-8092 | Imprint