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

TR95-009 | 2nd February 1995
Matthias Krause

A note on realizing iterated multiplication by small depth threshold circuits

It is shown that decomposition via Chinise Remainder does not
yield polynomial size depth 3 threshold circuits for iterated
multiplication of n-bit numbers. This result is achieved by
proving that, in contrast to multiplication of two n-bit
numbers, powering, division, and other related problems, the
... more >>>


TR95-008 | 27th January 1995
Nader Bshouty

Exact Learning Boolean Functions via the Monotone Theory


TR95-006 | 1st January 1995
Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

Pseudorandom Generators, Measure Theory, and Natural Proofs


This paper proves that if strong pseudorandom number generators or
one-way functions exist, then the class of languages that have
polynomial-sized circuits is not small within exponential
time, in terms of the resource-bounded measure theory of Lutz.
More precisely, if for some \epsilon > 0 there exist nonuniformly
2^{n^{\epsilon}}-hard ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint