Laboratory of Mathematical Logic

Пятница, 20 июня, комната 106. Начало в 16:00.

Докладчик: В. Н. Баргачёв (СПбГУ).

Тема: Эффективная конструкция множества перестановок, независимых по 4 относительно минимума.

Abstract

Семейства перестановок обладающие свойством независимости относительно минимума были введены в [1]. Такие семейства оказались полезны для нахождения "почти одинаковых" документов в поисковых системах типа Altavista. Независимые относительно минимума семейства перестановок находят и другие приложения, например при дерандомизации алгоритмов для некоторых NP-полных задач.

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

множества

называется независимым по

относительно минимума, если для любого непустого подмножества

множества

размера не более

и любого элемента

множества

, выполняется

.

Первые нетривиальные нижние оценки на размер независимого по k семейства перестановок появились в [2], [3]. В [2] доказывается существование независимого по k относительно минимума множества перестановок размера

. В [4] при

эта оценка улучшается до

. В данном докладе мы улучшаем эту оценку:

ТЕОРЕМА. Пусть

,

. Тогда существует независимое по 4 семейство перестановок множества

размера

.

Нужно отметить, что случаи малых k действительно интересны, так как используются для дерандомизации алгоритмов для задачи k-КНФ, а 3-КНФ является классической NP-полной задачей.

Литература

1. Broder A. Z., Charikar M., Frieze A. M., Mitzenmacher M. "Min-wise independent permutations" // J. Comput. System Sci., 2000, V. 60, P. 630-659.

2. Itoh T., Takei Y., Tarui J. "On permutations with limited independence" // Proc. of SODA'2000, 2000, P. 137-146.

3. Норин С. "Полиномиальная нижняя оценка на размер независимого по k относительно минимума семейства перестановок" // Зап. Научн. Сем. ПОМИ, 2001, Т. 277, С. 104-116.

4. Vsemirnov M. "Automorphisms of projective spaces and min-wise independent sets of permutations" // Quaderni del Seminario Mathematico di Brescia, 2002, N53, P. 1-16.