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

TR94-017 | 12th December 1994

Neural Nets with Superlinear VC-Dimension

It has been known for quite a while that the Vapnik-Chervonenkis dimension
(VC-dimension) of a feedforward neural net with linear threshold gates is at
most O(w log w), where w is the total number of weights in the neural net.
We show in this paper that this bound is in ... more >>>


TR94-011 | 12th December 1994
R. Beigel, W. Hurwood, N. Kahale

Fault Diagnosis in a Flash

We consider the fault diagnosis problem: how to use parallel testing
rounds to identify which processors in a set are faulty. We prove
that 4 rounds suffice when 3% or less of the processors are faulty,
and 4 rounds are necessary when any nontrivial constant fraction of
the processors are ... more >>>


TR94-010 | 12th December 1994
Alexander Razborov, Steven Rudich

Natural Proofs


We introduce the notion of {\em natural} proof.
We argue that the known proofs of lower bounds on the complexity of explicit
Boolean functions in non-monotone models
fall within our definition of natural.
We show based on a hardness assumption
that natural proofs can't prove superpolynomial lower bounds ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint