Пятница 09.11. В.В. Подольский (ВШЭ): "Нижние оценки в модели разрешающих деревьев с XOR-запросами"
PDMI seminars
Тема: Нижние оценки в модели разрешающих деревьев с XOR-запросами
Место: 106
Время: 09.11.2018, 14:00
Докладчик: В.В. Подольский (ВШЭ)
Abstract:
В докладе будет рассказано о новой оценке на сложность D(f) вычисления булевых функций в модели разрешающих деревьев с XOR запросами . В этой модели требуется вычислить известную булеву функцию f на неизвестном входе. За один запрос разрешается узнать XOR любого подмножества входных битов. Мерой сложности является число запросов в худшем случае.
Гранулярностью gran(f) булевой функции f называется минимальное натуральное k, такое что всякий коэффициент Фурье функции f выражается как целое число, умноженное на 1/2^k. Мы докажем, что D(f) ≥ gran(f)+1. Эта нижняя оценка является усилением оценок на D(f) через l_0-норму спектра Фурье f и через степень f как многочлена над GF(2). Используя новую оценку мы находим точное значение D(f) для некоторых важных функций f, включая функцию голосования и итерированную функцию голосования. Для функции голосования сложность оказывается равной n-B(n)+1, где B(n) равно числу единиц в двоичной записи n. Для итерированной функции голосования сложность равна (n+1)/2. Также мы приведем пример функции, для которой наша нижняя оценка не является точной. Из наших результатов вытекает новая нижняя оценка на мультипликативную сложность функции голосования. Доклад основан на совместной работе с Анастасией Чистопольской.