Given two n-variable boolean functions f and g, we study the problem of computing an -approximate isomorphism between them. I.e. a permutation of the n variables such that f(x1x2xn) and g(x(1)x(2)x(n)) differ on at most an fraction of all boolean inputs 01n . We give a randomized 2O(nlog(n)O(1)) algorithm that computes a 12log(n)O(1)-approximate isomorphism between two isomorphic boolean functions f and g that are given by depth d circuits of nO(1) size, where d is a constant independent of n. In contrast, the best known algorithm for computing an exact isomorphism between n-ary boolean functions has running time 2O(n) cite{Luks99} even for functions computed by nO(1) size DNF formulas. Our algorithm is based on a recent result for hypergraph isomorphism with bounded edge size cite{BabaiC08} and the classical Linial Mansour-Nisan result on approximating small depth and size boolean circuits by small degree polynomials using Fourier analysis.
展开▼
