On the Implementation of Huge Random Objects

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

Joint work with Oded Goldreich and Asaf Nussboim.

Short Biography:

Goldwasser is a coleader of the cryptography and information security
group and a member of the complexity theory group within the Theory of
Computation Group at the Laboratory for Computer Science at the
Massachusetts Institute of Technology, and a professor of computer science
in Weizmann Institute in Rehovot, Israel. She received her BA in applied
mathematics and computer science from Carnegie Mellon University and an MS
and PhD from the University of California at Berkeley in theoretical
computer science. Goldwasser is one of the inventors of zero-knowledge
proofs, a key primitive in the design of modern cryptographic protocols.
Her work on probabilistically checkable proofs has led to a number of
breakthroughs in complexity theory, including classifying the complexity
of approximation problems. Goldwasser has been awarded the ACM Grace
Murray Hopper Award for outstanding young computer professional of the
year and the RSA Award in Mathematics for outstanding mathematical
contributions to cryptography. She is a two-time winner of the Godel Prize
in Theoretical Computer Science and was elected to the American Academy of
Arts and Sciences in 2001.

Homepage: http://theory.lcs.mit.edu/~shafi/