Sublinear time algorithms in the theory of groups and semigroups.

MaRDI QIDQ716397zbMATH OpenFDO

Authors Vladimir Shpilrain

Publication date 28 April 2011

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.3252, https://projecteuclid.org/euclid.ijm/1299679745

zbMATH Keywords

algorithmic problemscomplexityprimitive elementssublinear time algorithmsword problem

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

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.

Review text

Sublinear time algorithms give some sort of an answer after inspecting only a small part of the input. The author considers several algorithmic problems in the theory of groups and semigroups that may admit sublinear time solution at least for ``most inputs.

Recommendations

• scientific article; zbMATH DE number 5057523
• Sublinear time algorithms
• Property testing and its connection to learning and approximation
• Property testing. Problems and techniques
• Finding cycles and trees in sublinear time

Cites work

• 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.
• 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?)
• 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

(8)

• DLP in semigroups: algorithms and lower bounds
• Sublinear time algorithms
• scientific article; zbMATH DE number 1004940 (Why is no real title available?)
• 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})\)
• Average-case complexity of the Whitehead problem for free groups
• Linear average-case complexity of algorithmic problems in groups
• Randomness and complexity in matrix groups

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)