  This work presents a Fourier analysis framework for the non-interactive
source simulation (NISS) problem. Two distributed agents observe a pair of
sequences $X^d$ and $Y^d$ drawn according to a joint distribution $P_{X^dY^d}$.
The agents aim to generate outputs $U=f_d(X^d)$ and $V=g_d(Y^d)$ with a joint
distribution sufficiently close in total variation to a target distribution
$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet
outputs is decidable. For the binary-output NISS, an upper-bound to the input
complexity was derived which is
$O(\exp\operatorname{poly}(\frac{1}{\epsilon}))$. In this work, the input
complexity and algorithm design are addressed in several classes of NISS
scenarios. For binary-output NISS scenarios with doubly-symmetric binary
inputs, it is shown that the input complexity is
$\Theta(\log{\frac{1}{\epsilon}})$, thus providing a super-exponential
improvement in input complexity. An explicit characterization of the simulating
pair of functions is provided. For general finite-input scenarios, a
constructive algorithm is introduced that explicitly finds the simulating
functions $(f_d(X^d),g_d(Y^d))$. The approach relies on a novel Fourier
analysis framework. Various numerical simulations of NISS scenarios with IID
inputs are provided. Furthermore, to illustrate the general applicability of
the Fourier framework, several examples with non-IID inputs, including
entanglement-assisted NISS and NISS with Markovian inputs are provided.
