Testing properties of functions on finite groups

DOI10.1002/RSA.20639MaRDI QIDQ2830241zbMATH OpenOpenAlexFDO

Authors Kenta Oono, Yuichi Yoshida

Publication date 9 November 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.00930

zbMATH Keywords

finite groupshomomorphismproperty testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Ordinary representations and characters (20C15) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Abstract: We study testing properties of functions on finite groups. First we consider functions of the form $f:GomathbbC$, 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:Go{M}_d(mathbbC)$, where $d$ is a fixed constant and $M_d(mathbbC)$ is the family of $d$ by $d$ matrices with each element in $mathbbC$. For a function $g:Go{M}_d(mathbbC)$, 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 $xinG$.

Recommendations

• Algebraic property testing: the role of invariance
• Testing linear-invariant function isomorphism
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

Cites work

• scientific article; zbMATH DE number 1974576 (Why is no real title available?)
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Algebraic property testing: the role of invariance
• Algorithmic and analysis techniques in property testing
• Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
• An Introduction to Lie Groups and Lie Algebras
• Derandomizing Homomorphism Testing in General Groups
• Every locally characterized affine-invariant property is testable
• Fourier theoretic probabilistic inference over permutations
• Linearity testing in characteristic two
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• On the Robustness of Functional Equations
• On the ``log rank-conjecture in communication complexity
• Optimal testing of Reed-Muller codes
• Partially symmetric functions are efficiently isomorphism testable
• Proof verification and the hardness of approximation problems
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Symmetric groups and expander graphs.

Cited in

(1)

• scientific article; zbMATH DE number 278890 (Why is no real title available?)

This page was built for publication: Testing properties of functions on finite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830241)