On the Implementation of Huge Random Objects
Webpage for a paper by Goldreich, Goldwasser and Nussboim
Abstract
We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good distance.
A pseudo-random implementation of such type T objects must generate
objects of type T that can not be distinguished from random ones,
rather than objects that can not be distinguished from
type T objects (although they are not type T at all).
We will model a type T object as a function, and access
objects by queries into these functions. We investigate
supporting both standard queries that only evaluates the
primary function at locations of the user's choice
(e.g., edge queries in a graph),
and complex queries that may ask for the result of a computation
on the primary function, where this computation is infeasible
to perform with a polynomial number of standard queries
(e.g., providing the next vertex along a Hamiltonian path in the graph).
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.