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

[PDMI seminars]

Семинар по дискретной математике

Тема: Hard instances, Dehn monsters, and complexity
Место: 203
Время: 12.05.2017, 18:00
Докладчик: Alexei Miasnikov (Stevens Institute)

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.