Nearly tight bounds for testing function isomorphism

Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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}n → {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}n → {0, 1} is Ω(k). (2) Isomorphism to any k-junta f : {0, 1}n → {0, 1} can be tested with O(klogk) queries. (3) For some k-juntas f : {0, 1} n → {0, 1}, testing isomorphism to f with one-sided error requires Ω(k log(n/k)) queries. In particular, testing whether f : {0, 1}n → {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}n → {0,1} is Θ(2n/). 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}n → {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.

Original languageEnglish (US)
Pages (from-to)459-493
Number of pages35
JournalSIAM Journal on Computing
Volume42
Issue number2
DOIs
StatePublished - Jul 18 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Boolean functions
  • Isomorphism
  • Property testing

Fingerprint Dive into the research topics of 'Nearly tight bounds for testing function isomorphism'. Together they form a unique fingerprint.

Cite this