In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.
We prove that for every $k \leq n$, the query complexity of testing isomorphism to $k$-juntas is
$\Omega(k)$ and $O(k \log k)$. In particular, the (worst-case) query complexity of testing isomorphism to a given function $f:\zo^n \to \zo$ is $\widetilde\Theta (n)$.
Prior to our work, only lower bounds of $\Omega( \log k)$ queries were known,
proved by Fischer et al. \cite{juntas}, Blais and O'Donnell
\cite{bl_od}, and recently by Alon and Blais \cite{alon_blais}. Our proof can also be extended to give polynomial query-complexity lower bounds for
the problems of testing whether a function has a circuit of size $\le s$,
and testing whether the Fourier degree of a function is $\le d$. This answers questions posed by Diakonikolas et al. \cite{til}.
The nearly tight $O(k \log k)$ upper bound improves the $\widetilde{O}(k^4)$ upper bound from \cite{juntas} (and the similar bound that follows from \cite{til}).
One implication of our techniques is a query-efficient procedure that given oracle access to any $k$-junta $g:\zo \to \zo$ can draw uniformly-random samples $(x,a) \in \zo^k \times \zo$ labelled by the core of $g$, each sample being correct with high probability. Generating such samples is one of the main ingredients of the testers from \cite{til}; while the procedure therein makes roughly $k$ queries to $g$ for obtaining each sample, our procedure requires only
{\em one} query to $g$.
We also study the query complexity of testing isomorphism to $k$-juntas with one-sided error. We
prove that for any $1 < k < n - 1$, the query complexity is $\Omega(\log {n \choose k})$, which is
almost optimal. This lower bound is obtained by proving that the query complexity of testing, with one-sided error, whether a function is a
$k$-parity is $\Theta(\log {n \choose k})$.
Finally, we consider the problem of testing isomorphism between two unknown functions that can be
queried. We prove that the (worst-case) query complexity in this setting is
$\Omega(\sqrt{2^n})$ and $O(\sqrt{ 2^n n \log n})$.
