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