TR10-093 Authors: Sourav Chakraborty, David GarcĂa Soriano, Arie Matsliah

Publication: 3rd June 2010 15:28

Downloads: 3433

Keywords:

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