Isomorphism testing of Boolean functions computable by constant-depth circuits
Given two n-variable Boolean functions f and g, we study the problem of computing an ?-approximate isomorphism between them. An ?-approximate isomorphism is a permutation ? of the n  Boolean variables such that f(x1,x2,,xn) f ( x 1 , x 2 ,  , x n ) and g(x?(1),x?(2),,x?(n)) g ( x ? ( 1 ) , x ? ( 2 ) ,  , x ? ( n ) ) differ on at most an ?  fraction of all Boolean inputs {0,1}n { 0 , 1 } n . We give a randomized 2 O ( n log ? ( n / ? ) O ( d ) ) time algorithm that computes an ?-approximate isomorphism between two isomorphic Boolean functions f and g that are given by depth d  circuits of poly(n) poly ( n ) size, where d is a constant independent of n, for any positive ?. In contrast, the best known algorithm for computing an exact isomorphism between n -ary Boolean functions has running time 2O(n) 2 O ( n ) [12] even for functions computed by poly(n) poly ( n ) size DNF formulas. Our algorithm is based on a result for hypergraph isomorphism with bounded edge size [4] and the classical LinialMansourNisan result on approximating small depth and size Boolean circuits by small degree polynomials using Fourier analysis [11].
isomorphism boolean functions constant-depth circuits