TY - GEN

T1 - Testing Boolean function isomorphism

AU - Alon, Noga

AU - Blais, Eric

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78149336315&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149336315&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15369-3_30

DO - 10.1007/978-3-642-15369-3_30

M3 - Conference contribution

AN - SCOPUS:78149336315

SN - 3642153682

SN - 9783642153686

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

SP - 394

EP - 405

BT - Approximation, Randomization, and Combinatorial Optimization

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

Y2 - 1 September 2010 through 3 September 2010

ER -