Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-093 | 3rd June 2010 15:26

Nearly Tight Bounds for Testing Function Isomorphism


Authors: Sourav Chakraborty, David GarcĂ­a Soriano, Arie Matsliah
Publication: 3rd June 2010 15:28
Downloads: 1910


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

ISSN 1433-8092 | Imprint