City: Saint Petersburg Novosibirsk Kazan Language: Русский English

k-независимые хеш-функции и их применения
Probabilistic methods in computations

What: Lecture
When: Sunday, 11 March 2012, 18:30–20:05
Where: ПОМИ РАН

Description

k-независимые хеш-функции, конструкции. Основная лемма о хешировании для попарно независимых хеш-функций. Лемма о хешировании для 2t-независимых хеш-функций. Сравнение сложности NP-задач. Приближенный подсчет числа подсказок.

Video