Laboratory of Mathematical Logic at PDMI

Пятница, 11 ноября, комната 106. Начало в 17:30.

Докладчик: С. Николенко.

Тема: Семейства слабо односторонних перестановок.

Abstract

Доклад по статье A. Hiltgen ``Constructions of Feebly-One-Way Families of Permutations''.

До сих пор ничего не известно о том, существуют ли настоящие односторонние функции, обратные к которым найти экспоненциально сложнее, чем вычислить сами функции. Слабо односторонние (feebly one-way) функции --- это функции, обратные к которым найти сложнее хотя бы в константное число раз (это число называется порядком соответствующего семейства функций). В докладе мы сначала явно построим семейство слабо односторонних функций порядка 3/2, а затем укажем общий метод, который позволит построить семейство слабо односторонних функций порядка 2.