Laboratory of Mathematical Logic at PDMI

Пятница, 12 мая, 203. Начало в 18:00.

Докладчик: Alexei Miasnikov (Stevens Institute).

Тема: Hard instances, Dehn monsters, and complexity.

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.