Efficient computation of approximate isomorphisms between Boolean functions

•A new algorithm for the construction of approximate ismorphisms between Boolean functions.•Improvement on an existing algorithm in several respects.•Efficiency: it works in polynomial time.•Performance: better performance guarantees as before.

Arvind and Vasudev [2] have introduced the notion of an approximate isomorphism between two Boolean functions f and g. They furthermore designed two algorithms that construct an approximate isomorphism when given oracle access to f and g  . The first of these algorithms is specialized to Boolean functions which are computable by constant-depth circuits. The second one applies to any pair of Boolean functions. It runs in exponential time and achieves optimality up to a factor of order n. In this paper, we present an improved analysis and come up with a variant of the second algorithm that runs in polynomial time and achieves optimality up to a factor of (approximately) 2.