Учитывая

11

Вот проблема с похожим вкусом к изучению хунт:

Входные данные: функция f:{0,1}n{1,1} , представленная оракулом членства, то есть оракулом, который дал x , возвращает f(x) .

Цель: Найти вложенный куб S из {0,1}n с объемом |S|=2nk такое, что |ExSf(x)|0.1 . Мы предполагаем, что такой субкуб существует.

Легко получить алгоритм, который работает за время nO(k) и возвращает правильный ответ с вероятностью , испробовав все способов выбора вложенного куба и выбрав среднее значение в каждом из них.( 2 н ) к0.99(2n)k

Мне интересно найти алгоритм, который работает во времени . Как вариант, нижняя граница была бы отличной. Эта проблема похожа на изучение хунт, но я не вижу реальной связи между их вычислительной сложностью.poly(n,2k)

Обновление: @ Томас ниже доказывает, что примерная сложность этой проблемы - . Тем не менее, интересной проблемой является вычислительная сложность проблемы.poly(2k,logn)

Изменить: для простоты можно предположить, что существует вложенный куб с |ExSf(x)|0.2 (обратите внимание на разрыв: мы ищем субкуб со средним значением 0.1 .) Я почти уверен, что любое решение проблемы с разрывом также решит проблему без зазора.

пельмени мобиус
источник

Ответы:

7

Вот лучшая оценка сложности образца. (Хотя сложность вычислений все еще .)nk

Теорема. Предположим, что существует субкуб размером 2 n - k такой, что | E x S [ f ( x ) ] | 0,12 . С помощью O ( 2 kk log n ) выборок мы можем с высокой вероятностью идентифицировать субкуб S ' размером 2 n - k такой, что | E x S [ fS2nk|ExS[f(x)]|0.12O(2kklogn)S2nk .|ExS[f(x)]|0.1

Обратите внимание на небольшую потерю параметров ( является оптимальным по сравнению с гарантией 0,1 ).0.120.1

Доказательство. Pick точек P { 0 , 1 } п равномерно по случайному и запросу F при каждом х P .mP{0,1}nfxP

Зафиксируйте субкуб размером 2 n - k . У нас есть E [ | S P | ] = м 2 - к . По черновской границе P [ | S P | < m 2 - k - 1 ] 2 - Ω ( м 2 - k ) . Также P [ | E x S S2nkE[|SP|]=m2k

P[|SP|<m2k1]2Ω(m2k).
P[|ExSP[f(x)]ExS[f(x)]|>ε]2Ω(|SP|ε2).

Объединением, объединенным над всеми вариантовS, мы имеемP[S| ExSP[f(x)]-ExS[f(x)]| ε]1- ( n(nk)2kSТаким образомвыбираят=O(2K/ε2Kвойтип), мы можем обеспечить, чтобы с вероятностьюпо меньшей мере0,99, можно оценитьЕхS[F(х)]с точностьюεдля всех подкубовSиз размер2н-к

P[S  |ExSP[f(x)]ExS[f(x)]|ε]1(nk)2k2Ω(m2kε2).
m=O(2k/ε2klogn)0.99ExS[f(x)]εS2nk,

Полагая , докажем теорему: выбираем субкуб с наибольшим | E x S P [ f ( x ) ] | с высокой вероятностью выполнит требования. QEDε=0.01|ExSP[f(x)]|

Томас
источник
1
C2kCCnk
3
Еще один способ увидеть это состоит в том, что пространство диапазона, которое вы описываете, имеет ограниченную размерную дробь и, следовательно, ограниченную размерность VC, а затем вы бросаете в нее теорему eps-аппроксимации.
Суреш Венкат