Partially Symmetric Functions are Efficiently Isomorphism-Testable

Eric Blais, Amit Weinstein, Yuichi Yoshida

Given a function f: {0,1}^n \to {0,1}, the f-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to f up to relabeling of the in…