Douglas R. Stinson

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 >>>

Oded Goldreich, Avi Wigderson

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.

Oded Goldreich, Salil Vadhan

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 >>>

Philipp Woelfel

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 >>>