Testing properties of functions on finite groups
Kenta Oono, Yuichi Yoshida · Random Structures and Algorithms · 2016
Abstract We study testing properties of functions on finite groups. First we consider functions of the form , whereGis a finite group. We show that conjugate invariance, homomorphism, and the property of being proportional to an irreducible character is testable with a constant number of queries tof, where a character is a crucial notion in representation theory. Our proof relies on representation theory and harmonic analysis on finite groups. Next we consider functions of the form , wheredis a fixed constant and is the family ofdbydmatrices with each element in . For a function , we show that the unitary isomorphism togis testable with a constant number of queries tof, where we say thatfandgare unitary isomorphic if there exists a unitary matrixUsuch that for any . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 579–598, 2016