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-019 | 14th April 1995
Jin-Yi Cai, Alan L. Selman

Average time complexity classes


TR95-018 | 27th March 1995
Jay Belanger, Jie Wang

Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions

We show that polynomially rankable distributions
do not provide harder instances than uniform distributions
for NP problems. In particular, we show that if Levin's
randomized tiling problem is solvable in polynomial time on
average, then every NP problem under any p-rankable
... more >>>


TR95-017 | 27th March 1995
Claudia Bertram, Thomas Hofmeister

Multiple Product Modulo Arbitrary Numbers

We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint