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-028 | 9th June 1995
Eric Allender, Martin Strauss

Measure on P: Robustness of the Notion

In (Allender and Strauss, FOCS '95), we defined a notion of
measure on the complexity class P (in the spirit of the work of (Lutz,
JCSS '92) that provides a notion of measure on complexity classes at least
as large as E, and the work of (Mayordomo, Phd. ... more >>>


TR95-027 | 30th May 1995
Frederic Green

Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

We say an integer polynomial $p$, on Boolean inputs, weakly
$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod
$m$), whenever $f$ is zero. In this paper we prove that if a polynomial
weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$
more >>>


TR95-026 | 7th June 1995
Claus-Peter Schnorr, Horst Helmut Hoerner

Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

We introduce new algorithms for lattice basis reduction that are
improvements of the LLL-algorithm. We demonstrate the power of
these algorithms by solving random subset sum problems of
arbitrary density with 74 and 82 many weights, by breaking the
Chor-Rivest cryptoscheme in dimensions 103 and 151 ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint