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

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