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

Домашнее задание, срок сдачи 15.03.2015 (27 апреля исправлены задачи 6б и 9).