Revision #1 Authors: Oded Goldreich, Asaf Nussboim

Accepted on: 20th July 2003 00:00

Downloads: 1543

Keywords:

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

TR03-045 Authors: Oded Goldreich, Asaf Nussboim

Publication: 11th June 2003 08:52

Downloads: 1587

Keywords:

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