Sublinear time algorithms in the theory of groups and semigroups.

zbMATH Open1234.20044arXiv1105.3252MaRDI QIDQ716397FDOQ716397

Vladimir Shpilrain

Publication date: 28 April 2011

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

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.

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

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

zbMATH Keywords

complexityprimitive elementsword problemalgorithmic problemssublinear time algorithms

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Introductory notes on Richard Thompson's groups
• Property testing and its connection to learning and approximation
• ALGORITHMIC PROBLEMS IN VARIETIES
• Efficient testing of large graphs
• Braids, Links, and Mapping Class Groups. (AM-82)
• Title not available (Why is that?)
• Free differential calculus. IV: The quotient groups of the lower central series
• Combinatorial group theory.
• Generic-case complexity, decision problems in group theory, and random walks.
• Beziehungen zwischen Gruppen und Idealen in einem speziellen Ring
• Expected Computation Time for Hamiltonian Path problem
• Title not available (Why is that?)
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• On the distance between the expressions of a permutation
• Subsemigroups of nilpotent groups
• MAGNUS EMBEDDINGS FOR SEMIGROUPS
• Relatively free semigroups of intermediate growth

Cited In (6)

• Randomness and complexity in matrix groups
• DLP in semigroups: algorithms and lower bounds
• Subgroups of minimal index in polynomial time
• Average-case complexity of the Whitehead problem for free groups
• On two-generator subgroups in \(\mathrm{SL}_2(\mathbb{Z})\), \(\mathrm{SL}_2(\mathbb{Q})\), and \(\mathrm{SL}_2(\mathbb{R})\)
• Title not available (Why is that?)

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)