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-005 | 12th December 1994
Noga Alon, Alan Frieze, Dominic Welsh

Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$
encodes numerous interesting combinatorial quantities associated
with the graph. Its evaluation in various points in the $(x,y)$
plane give the number of spanning forests of the graph, the number
of its strongly connected orientations, the number of its proper
$k$-colorings, the (all ... more >>>


TR94-002 | 12th December 1994
Oded Goldreich, Avi Wigderson

Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

We present three explicit constructions of hash functions,
which exhibit a trade-off between the size of the family
(and hence the number of random bits needed to generate a member of the family),
and the quality (or error parameter) of the pseudo-random property it
achieves. Unlike previous constructions, ... more >>>


TR94-001 | 12th December 1994
Noam Nisan, Avi Wigderson

On Rank vs. Communication Complexity

This paper concerns the open problem of Lovasz and
Saks regarding the relationship between the communication complexity
of a boolean function and the rank of the associated matrix.
We first give an example exhibiting the largest gap known. We then
prove two related theorems.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint