We consider the function ensembles emerging from the
construction of Goldreich, Goldwasser and Micali (GGM),
when applied to an arbitrary pseudoramdon generator.
We show that, in general, such functions
fail to yield correlation intractable ensembles.
Specifically, it may happen that, given a description of such a ... more >>>

We survey some recent results on the complexity of computing
approximate solutions for instances of the Minimum Bisection problem
and formulate some intriguing and still open questions about the
approximability status of that problem. Some connections to other
optimization problems are also indicated.

more >>>

We show how to efficiently transform any public coin honest verifier
zero knowledge proof system into a proof system that is concurrent
zero-knowledge with respect to any (possibly cheating) verifier via
black box simulation. By efficient we mean that our transformation
incurs only an additive overhead, ... more >>>