Isomorphism testing of Boolean functions computable by constant-depth circuits

Given two -variable Boolean functions and , we study the problem of computing an - between them. An - is a permutation of the Boolean variables such that and differ on at most an fraction of all Boolean inputs . We give a randomized time algorithm that computes an -approximate isomorphism between two isomorphic Boolean functions and that are given by depth circuits of size, where is a constant independent of , for any positive . In contrast, the best known algorithm for computing an between -ary Boolean functions has running time even for functions computed by size DNF formulas. Our algorithm is based on a result for hypergraph isomorphism with bounded edge size and the classical Linial–Mansour–Nisan result on approximating small depth and size Boolean circuits by small degree polynomials using Fourier analysis .