Sublinear time algorithms in the theory of groups and semigroups

Details Sublinear time algorithms in the theory of groups and semigroups Sublinear time algorithms in the theory of groups and semigroups

2011-05-17

arxiv.org/abs/1105.3252v1

Illinois J. Math. 54 (2011), 187---197

Mathematics

Group Theory

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sublinear time algorithms in the theory of groups and semigroups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear time algorithms in the theory of groups and semigroups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear time algorithms in the theory of groups and semigroups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727587