  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.
