75 KAM Mathematical Colloquium

Abstract

I will survey results about computational complexity of the word problem in groups and its relation with isoperimetric function and other asymptotic geometry invariants of groups. A typical result (joint with Birget, Olshanskii, Rips): the word problem of a finitely generated group is in NP if and only if the group embeds into a finitely presented group with polynomial isoperimetric function.
 

O přednášejícím

Mark Sapir studoval ve Sverdlovsku (nyní Jekaterinburg) a v Moskvě. Ihned po doktorátu pracoval jako docent na universitě ve Sverdlovsku a od roku 1991 v USA. V současnosti je Centennial professor na Vanderbiltově universitě v Nashvillu. Mark Sapir byl hostem předních mezinárodních ústavů, mezi nimiž zmiňme opakované pobyty na IHES Bur-Sur-Yvette, na Max Planckově institutu v Bonnu, Hebrejské universitě v Jeruzalémě a zmiňme rovněž Simmonsovu profesuru na MSRI v Ber- keley. Mark Sapir je členem redakčních rad 5 mezinárodních časopisů. V roce 2006 přednesl zvanou přednášku na Mezinárodním kongresu matematiků v Madridu.

Přes jeho mnohostrannou činnost lze říci, že hlavním oborem Marka Sapira je teorie grup, zvláště pak geometrická a asymptotická teorie grup včetně souvisejících algoritmických problémů. Z této oblasti je jeho pražské kolokvium.

Zmiňme však také, že Mark Sapir je i známým autorem pedagogicky zaměřených textů a software. Je též velmi aktivní při výchově mladých nadaných informatiků a matematiků, jak na úrovni gymnázií tak universitní. Jeho učebnice informatiky pro střední školy z roku 1990 vyšla v mnoha vydáních a celkový náklad překročil 2 mil. výtisků. To je u matematického a informatického textu nevídané!