Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR03-045 | 20th July 2003 00:00

On the Implementation of Huge Random Objects Revision of: TR03-045

RSS-Feed




Revision #1
Authors: Oded Goldreich, Asaf Nussboim
Accepted on: 20th July 2003 00:00
Downloads: 1845
Keywords: 


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


Paper:

TR03-045 | 8th June 2003 00:00

On the Implementation of Huge Random Objects





TR03-045
Authors: Oded Goldreich, Asaf Nussboim
Publication: 11th June 2003 08:52
Downloads: 1840
Keywords: 


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



ISSN 1433-8092 | Imprint