✦ LIBER ✦

Generic-case complexity, decision problems in group theory, and random walks

✍ Scribed by Ilya Kapovich; Alexei Myasnikov; Paul Schupp; Vladimir Shpilrain

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 258 KB
Volume: 264
Category: Article
ISSN: 0021-8693
DOI: 10.1016/s0021-8693(03)00167-4

No coin nor oath required. For personal study only.

✦ Synopsis

We give a precise definition of "generic-case complexity" and show that for a very large class of finitely generated groups the classical decision problems of group theory-the word, conjugacy, and membership problems-all have linear-time generic-case complexity. We prove such theorems by using the theory of random walks on regular graphs.

📜 SIMILAR VOLUMES

Generic behavior of the density of state

Generic behavior of the density of states in random matrix theory and equilibrium problems in the presence of real analytic external fields

✍ A. B. J. Kuijlaars; K. T-R McLaughlin 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 2 views

The equilibrium measure in the presence of an external field plays a role in a number of areas in analysis, for example, in random matrix theory: The limiting mean density of eigenvalues is precisely the density of the equilibrium measure. Typical behavior for the equilibrium measure is: 1. it is p