### Abstract

Two boolean functions f, g : {0,1} ^{n} →{0,1} are isomorphic if they are identical up to relabeling of the input variables. We consider the problem of testing whether two functions are isomorphic or far from being isomorphic with as few queries as possible. In the setting where one of the functions is known in advance, we show that the non-adaptive query complexity of the isomorphism testing problem is Θ(n). In fact, we show that the lower bound of Ω(n) queries for testing isomorphism to g holds for almost all functions g. In the setting where both functions are unknown to the testing algorithm, we show that the query complexity of the isomorphism testing problem is Θ(2^{n/2}). The bound in this result holds for both adaptive and non-adaptive testing algorithms.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings |

Pages | 394-405 |

Number of pages | 12 |

DOIs | |

State | Published - Nov 15 2010 |

Externally published | Yes |

Event | 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 - Barcelona, Spain Duration: Sep 1 2010 → Sep 3 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6302 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010 |
---|---|

Country | Spain |

City | Barcelona |

Period | 9/1/10 → 9/3/10 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Testing Boolean function isomorphism'. Together they form a unique fingerprint.

## Cite this

*Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings*(pp. 394-405). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6302 LNCS). https://doi.org/10.1007/978-3-642-15369-3_30