  This work initiates the systematic study of explicit distributions that are
indistinguishable from a single exponential-size combinatorial object. In this
we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that
focused on the implementation of huge objects that are indistinguishable from
the uniform distribution, satisfying some global properties (which they coined
truthfulness). Indistinguishability from a single object is motivated by the
study of generative models in learning theory and regularity lemmas in graph
theory. Problems that are well understood in the setting of pseudorandomness
present significant challenges and at times are impossible when considering
generative models of huge objects.
  We demonstrate the versatility of this study by providing a learning
algorithm for huge indistinguishable objects in several natural settings
including: dense functions and graphs with a truthfulness requirement on the
number of ones in the function or edges in the graphs, and a version of the
weak regularity lemma for sparse graphs that satisfy some global properties.
These and other results generalize basic pseudorandom objects as well as
notions introduced in algorithmic fairness. The results rely on notions and
techniques from a variety of areas including learning theory, complexity
theory, cryptography, and game theory.
