Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with universal hashing:
TR95-052 | 4th October 1995
Douglas R. Stinson

On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
... more >>>

TR96-041 | 24th July 1996
Oded Goldreich, Avi Wigderson

On the Circuit Complexity of Perfect Hashing

Revisions: 1 , Comments: 2

We consider the size of circuits which perfectly hash
an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$
into $\bitset^m$.
We observe that, in general, the size of such circuits is
exponential in $2k-m$,
and provide a matching upper bound.

more >>>

TR98-063 | 4th November 1998
Oded Goldreich, Salil Vadhan

Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

We consider the following (promise) problem, denoted ED (for Entropy
Difference): The input is a pairs of circuits, and YES instances (resp.,
NO instances) are such pairs in which the first (resp., second) circuit
generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

TR00-046 | 19th June 2000
Philipp Woelfel

New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

Ordered binary decision diagrams (OBDDs) belong to the most important
representation types for Boolean functions. Although they allow
important operations such as satisfiability test and equality test to
be performed efficiently, their limitation lies in the fact, that they
may require exponential size for important functions. Bryant ... more >>>

ISSN 1433-8092 | Imprint