We study the problem of testing structural equivalence (isomorphism) between a pair of Boolean functions $f,g:\\{0,1\\}^n \\to \\{0,1\\}$. 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:\\{0,1\\}^n \\to \\{0,1\\}$ is $\\widetilde\\Theta (n)$.
Thus our bounds are nearly tight. Our lower bound and upper bound results improves the known bound obtained by Fischer et al. (2004), Blais and O'Donnell (2010), and recently by Alon and Blais (2010).
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 $< s$, and testing whether the Fourier degree of a function is $\\le d$. This answers questions posed by Diakonikolas et al. (2007).
One implication of our techniques is a query-efficient procedure that given oracle access to any $k$-junta $g:\\{0,1\\} \\to \\{0,1\\}$ can draw uniformly-random samples $(x,a) \\in \\{0,1\\}^k \\times \\{0,1\\}$ 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 Diakonikolas et al. (2007) while the procedure therein makes roughly $k$ queries to $g$ for obtaining each sample, our procedure requires only 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})$.
We also 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})$ (this is a joint work with Arie Matsliah and David Garcia Soriano).
