Junto-symmetric functions, hypergraph isomorphism and crunching

Abstract

We make a step towards characterizing the boolean functions to which isomorphism can be efficiently tested. Specifically, we prove that isomorphism to any boolean function on {0, 1} n with a polynomial number of distinct permutations can be tested with a number of queries that is independent of n. We also show some partial results in the converse direction, and discuss related problems: testing isomorphism up to linear transformations, and testing isomorphism against a uniform (hyper)graph that is given in advance. Our results regarding the latter topic generalize a theorem of Fischer (SICOMP 2005), and in the process we also provide a simpler proof of his original result which avoids the use of Szemerédi's regularity lemma. © 2012 IEEE.