|
|
|
|
Workshop:
Introduction to Generic Complexity | | | |
|
|
| Kapovich, Ilya; Myasnikov, Alexei; Schupp, Paul; Shpilrain, Vladimir. Generic-case complexity, decision problems in group theory, and random walks. J. Algebra 264 (2003), no. 2, 665--694. |
| The generic complexity of decision problems from combinatorial group theory is defined. For a large class groups the generic time complexity of the word, conjugacy and membership problem, is shown to be linear.
|
|
| Borovik, Alexandre V.; Myasnikov, Alexei G.; Shpilrain, Vladimir. Measuring sets in infinite groups. Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), 21--42, Contemp. Math., 298, Amer. Math. Soc., Providence, RI, 2002. |
| A discussion of various ways to define probability on countable groups. Includes a section on asymptotic density.
|
|
| Kapovich, Ilya; Myasnikov, Alexei; Schupp, Paul; Shpilrain, Vladimir. Average-case complexity and decision problems in group theory. Adv. Math. 190 (2005), no. 2, 343--359. |
| Estimates of generic complexity are used to show that under certain circumstances if the worst case complexity of the word problem of a group is subexponential, then the average case complexity is linear.
|
|
| Kapovich, Ilya; Rivin, Igor; Schupp, Paul; Shpilrain, Vladimir. Asymptotic density in free groups and Z^k, Visible Points and Test Elements, http://xxx.lanl.gov/pdf/math.GR/0507573. |
| Certain subsets of free groups are shown to have asymptotic density strictly between 0 and 1.
|
|
|
|
|
Add new bibliography item
|
|
|
|
|
