Nearly tight bounds for testing function isomorphism

We study the problem of testing isomorphis m (equivalence up to relabeling of the input variables) between Boolean functions. We prove the following: (1) For most functions f : {0, 1}ⁿ → {0, 1}, the query complexity of testing isomorphism to f is Ω(n). Moreover, the query complexity of testing isomorphism to most k-juntas f : {0, 1}ⁿ → {0, 1} is Ω(k). (2) Isomorphism to any k-junta f : {0, 1}ⁿ → {0, 1} can be tested with O(klogk) queries. (3) For some k-juntas f : {0, 1} ⁿ → {0, 1}, testing isomorphism to f with one-sided error requires Ω(k log(n/k)) queries. In particular, testing whether f : {0, 1}ⁿ → {0, 1} is a k-parity with one-sided error requires Ω(k log(n/k)) queries. (4) The query complexity of testing isomorphism between two unknown functions f,g : {0, 1}ⁿ → {0,1} is Θ(2ⁿ/). These bounds are tight up to logarithmic factors, and they significantly strengthen the bounds proved by Fischer, Kindler, Ron, Safra, and Samorodnitsky [J. Comput. System Sci., 68 (2004), pp. 753-787] and Blais and O'Donnell [Proceedings of the IEEE Conference on Computational Complexity, 2010, pp. 235-246]. We also obtain results closely related to isomorphism testing, answering a question posed by Diakonikolas, Lee, Matulef, Onak, Rubinfeld, Servedio, and Wan [Proceedings of the IEEE Symposium on Foundations of Computer Science, 2007, pp. 549-558]: testing whether a function f : {0, 1}ⁿ → {0, 1} can be computed by a circuit of size ≤ s requires s^Ω(1) queries. All of our lower bounds apply to general (adaptive) testers.