Testing Boolean function isomorphism

Noga Alon, Eric Blais

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

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 Θ(2n/2). The bound in this result holds for both adaptive and non-adaptive testing algorithms.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings
Pages394-405
Number of pages12
DOIs
StatePublished - 2010
Event13th 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 2010Sep 3 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6302 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010
CountrySpain
CityBarcelona
Period9/1/109/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