Testing properties of functions on finite groups

DOI10.1002/RSA.20639zbMATH Open1377.20013arXiv1509.00930OpenAlexW2964058770MaRDI QIDQ2830241FDOQ2830241

Authors: Kenta Oono, Yuichi Yoshida 

Publication date: 9 November 2016

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

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$.

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

Recommendations

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

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)