Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR00-002 | 23rd December 1999
Michael Schmitt

Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks

We calculate lower bounds on the size of sigmoidal neural networks
that approximate continuous functions. In particular, we show that
for the approximation of polynomials the network size has to grow
as $\Omega((\log k)^{1/4})$ where $k$ is the degree of the polynomials.
This bound is ... more >>>


TR00-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>


TR99-048 | 7th December 1999
Beate Bollig, Ingo Wegener

Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

Ordered binary decision diagrams (OBDDs) are nowadays the
most common dynamic data structure or representation type
for Boolean functions. Among the many areas of application
are verification, model checking, and computer aided design.
For many functions it is easy to estimate the OBDD ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint