Testing properties of functions on finite groups

详细信息    查看全文

• 作者：Kenta Oono and Yuichi Yoshida
• 刊名：Random Structures & Algorithms
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：49
• 期：3
• 页码：579-598
• 全文大小：173K
• ISSN：1098-2418

文摘

We study testing properties of functions on finite groups. First we consider functions of the form f:G→ℂ, where G is 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 to f, 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 f:G→Md(ℂ), where d is a fixed constant and Md(ℂ) is the family of d by d matrices with each element in ℂ. For a function g:G→Md(ℂ), we show that the unitary isomorphism to g is testable with a constant number of queries to f, where we say that f and g are unitary isomorphic if there exists a unitary matrix U such that f(x)=Ug(x)U−1 for any x∈G.