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 ( x 1, x 2, …, x n ) and g ( x π ( 1 ), x π ( 2 ), …, x π ( n ) ) differ on at most an ε fraction of all Boolean inputs { 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 ) 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 2 O ( n ) [12] even for functions computed by poly ( n ) size DNF formulas. Our algorithm is based on a result for hypergraph isomorphism with bounded edge size [4] and the classical Linial–Mansour–Nisan result on approximating small depth and size Boolean circuits by small degree polynomials using Fourier analysis [11].

Authors

• V. Arvind
• Yadu Vasudev

Keywords

• Constant-depth circuits
• Boolean functions
• Isomorphism