Atlas home || Conferences | Abstracts | about Atlas

International Conference on Modern Algebra in conjunction with the 17th annual Shanks Lectures
May 21-24, 2002
Vanderbilt University
Nashville, TN, USA

Organizers
Jonathan Farley, Ralph Freese, Matthew Gould, Peter Jipsen, George McNulty, Miklos Maroti, Alexander Ol'shanskii, Steven Tschantz, Constantine Tsinakis, Matthew Valeriote

View Abstracts
Conference Homepage

Generic-case complexity of algorithmic problem in group theory
by
Ilya Kapovich
University of Illinois at Urbana-Champaign
Coauthors: Alexei Myasnikov, Paul Schupp, Vladimir Shpilrain

We introduce the notion of "generic-case" complexity for algorithmic problems, which reflects the performance of an algorithm on "most" inputs of a problem. We show that the known results about random walks on regular graphs imply that such traditional group theoretic problems as the word problem, the membership problem and the conjugacy problem, typically have linear "generic-case" complexity (even for the groups where the worst-case complexity is very high).

Date received: March 12, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caig-85.