This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

In this paper we consider a new type of cryptographic scheme, which can decode concealed
images without any cryptographic computations. The scheme is perfectly secure and very …

But, perhaps, we should start with a few words about graphs in general. They are, of course,
one of the prime objects of study in Discrete Mathematics. However, graphs are among the …

Classical fingerprinting associates with each string a shorter string (its fingerprint), such that
any two distinct strings can be distinguished with small error by comparing their fingerprints …

We describe a novel randomized method. the method of cobm-coding for finding simple
paths and cycles of a specified length k, and other small subgraphs, within a gwen graph …

Using expander graphs, we construct a new family of asymptotically good, linear error-
correcting codes. These codes have linear time sequential decoding algorithms and …

We show how to efficiently construct a small probability space on n binary random variables
such that for every subset, its parity is either zero or one with" almost" equal probability. They …

This paper discusses methods for assigning code-words for the purpose of fingerprinting
digital data, eg, software, documents, music, and video. Fingerprinting consists of uniquely …

We give cryptographic schemes that help trace the source of leaks when sensitive or
proprietary data is made available to a large set of parties. This is particularly important for …

We present three alternative simple constructions of small probability spaces on n bits for
which any k bits are almost independent. The number of bits used to specify a point in the …