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

TR99-023 | 16th June 1999
Amir Shpilka, Avi Wigderson

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero


In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for ... more >>>


TR99-022 | 14th June 1999
Eli Ben-Sasson, Avi Wigderson

Short Proofs are Narrow - Resolution made Simple

The width of a Resolution proof is defined to be the maximal number of
literals in any clause of the proof. In this paper we relate proof width
to proof length (=size), in both general Resolution, and its tree-like
variant. The following consequences of these relations reveal width as ... more >>>


TR99-021 | 8th April 1999
Igor E. Shparlinski

ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

We show that a pseudo-random number generator,
introduced recently by M. Naor and O. Reingold,
possess one more attractive and useful property.
Namely, it is proved that for almost all values of parameters it
produces a uniformly distributed sequence.
The proof is based on some recent bounds of exponential
more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint