## 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 Θ(2^{n}/). 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 language | English (US) |
---|---|

Pages (from-to) | 459-493 |

Number of pages | 35 |

Journal | SIAM Journal on Computing |

Volume | 42 |

Issue number | 2 |

DOIs | |

State | Published - Jul 18 2013 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Keywords

- Boolean functions
- Isomorphism
- Property testing