期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean
functions fg:\zon\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 kn, the query complexity of testing isomorphism to k-juntas is
(k) and O(klogk). In particular, the (worst-case) query complexity of testing isomorphism to a given function f:\zon\zo is (n).
Prior to our work, only lower bounds of (logk) 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 s,
and testing whether the Fourier degree of a function is d. This answers questions posed by Diakonikolas et al. \cite{til}.
The nearly tight O(klogk) upper bound improves the O(k4) 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\zo can draw uniformly-random samples (xa)\zok\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 1kn−1, the query complexity is (logkn) , 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 (logkn) .
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
(2n) and O(2nnlogn) .
