Пятница 12.05. Alexei Miasnikov (Stevens Institute): "Hard instances, Dehn monsters, and complexity"

Speaker: 
Alexei Miasnikov (Stevens Institute)
Date: 
Friday, May 12, 2017 - 18:00
Place: 
203
Abstract: 

In this talk I will focus on two seemingly different directions in modern algorithmic group theory: finding more and more efficient algorithms and how to find "hard" instances of the problems, how to amplify hardness, and how to measure hardness of the algorithms. The talk is intended to be non-technical, I will emphasize some relations between algorithmic group theory and cryptography.