Testability in group theory
In the paper under review, the authors study property testing problems concerning relations between permutations. In such problems, the input is a tuple \((\sigma_{1}, \dots, \sigma_{d})\) of permutations on \(\Omega=\{1, \dots, n \}\), and one wishes to determine whether this tuple satisfies a certain system of relations \(E\), or is far from every tuple that satisfies \(E\). If this computational problem can be solved by querying only a small number of entries of the given permutations, then the author says that \(E\) is testable. For example, when \(d=2\) and \(E\) consists of the single relation \(\mathsf{XY} = \mathsf{YX}\), this corresponds to testing whether \(\sigma_{1}\) and \(\sigma_{2}\) commutes. In [Int. Math. Res. Not. 2021, No. 20, 15574--15632 (2021; Zbl 07456010)], the first and the third author showed that set \(E=\{\mathsf{XY} = \mathsf{YX}\}\) is testable (on the other hand, the systems \(E = \{\mathsf{XZ} = \mathsf{ZX}, \mathsf{YZ} = \mathsf{ZY}\}\) and \(E=\{\mathsf{X}^{2}\mathsf{Y}=\mathsf{YX}^{2} \}\) are not testable). In the paper under review, the authors associate each system \(E\) with a group \(\Gamma=\Gamma_{E}\) and show that the testability of \(E\) depends only on \(\Gamma\) (just like in Galois theory where the solvability of a polynomial is determined by the solvability of the associated group).
- Algorithms for permutability in finite groups.
- scientific article; zbMATH DE number 2156274
- Fast property testing and metrics for permutations
- Every hereditary permutation property is testable
- scientific article; zbMATH DE number 2059223
- Fast recognition of alternating and symmetric Galois groups
- scientific article; zbMATH DE number 1819631
- Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups
- A large lower bound on the query complexity of a simple Boolean function
- Relational Properties Expressible with One Universal Quantifier Are Testable
- Abelian Groups Are Polynomially Stable
- Almost commuting permutations are near commuting permutations
- Almost solutions of equations in permutations.
- An amenable equivalence relation is generated by a single transformation
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Ergodic theory of amenable group actions. I: The Rohlin lemma
- Every property of hyperfinite graphs is testable
- Finitary approximations of groups and their applications
- Finite graphs and amenability
- Flexible stability and nonsoficity
- Group stability and property (T)
- Infinitely presented permutation stable groups and invariant random subgroups of metabelian groups
- Introduction to Property Testing
- Inverse and stability theorems for approximate representations of finite groups
- On the automorphism group of generalized Baumslag-Solitar groups.
- On the Cayley graph of a generic finitely presented group
- OPERATOR ALGEBRAIC APPROACH TO INVERSE AND STABILITY THEOREMS FOR AMENABLE GROUPS
- Processes on unimodular random networks
- Property of defect diminishing and stability
- Stability and invariant random subgroups
- Stability for product groups and property \(( \tau )\)
- Stability, cohomology vanishing, and nonapproximable groups
- The structure of the Torelli group. I: A finite set of generators for \({\mathcal I}\)
- Uncountably many permutation stable groups
- Über \(n\)-dimensionale Gittertransformationen
This page was built for publication: Testability in group theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076186)
