Sublinear time algorithms in the theory of groups and semigroups.
From MaRDI portal
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40)
Abstract: Sublinear time algorithms represent a new paradigm in computing, where an algorithm must give some sort of an answer after inspecting only a small portion of the input. The most typical situation where sublinear time algorithms are considered is property testing. There are several interesting contexts where one can test properties in sublinear time. A canonical example is graph colorability. To tell that a given graph is not k-colorable, it is often sufficient to inspect just one vertex with incident edges: if the degree of a vertex is greater than k, then the graph is not k-colorable. It is a challenging and interesting task to find algebraic properties that could be tested in sublinear time. In this paper, we address several algorithmic problems in the theory of groups and semigroups that may admit sublinear time solution, at least for "most" inputs.
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1342244 (Why is no real title available?)
- scientific article; zbMATH DE number 5057523 (Why is no real title available?)
- ALGORITHMIC PROBLEMS IN VARIETIES
- Beziehungen zwischen Gruppen und Idealen in einem speziellen Ring
- Braids, Links, and Mapping Class Groups. (AM-82)
- Combinatorial group theory.
- Efficient testing of large graphs
- Expected Computation Time for Hamiltonian Path problem
- Free differential calculus. IV: The quotient groups of the lower central series
- Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
- Generic-case complexity, decision problems in group theory, and random walks.
- Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
- Introductory notes on Richard Thompson's groups
- MAGNUS EMBEDDINGS FOR SEMIGROUPS
- On the distance between the expressions of a permutation
- Property testing and its connection to learning and approximation
- Relatively free semigroups of intermediate growth
- Subsemigroups of nilpotent groups
Cited in
(7)- scientific article; zbMATH DE number 1004940 (Why is no real title available?)
- Average-case complexity of the Whitehead problem for free groups
- Sublinear time algorithms
- Randomness and complexity in matrix groups
- Subgroups of minimal index in polynomial time
- On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\)
- DLP in semigroups: algorithms and lower bounds
This page was built for publication: Sublinear time algorithms in the theory of groups and semigroups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716397)
