Случайные ограничения и связь с полным влиянием булевых функций

9

Скажем, у нас есть булева функция f:{1,1}n{1,1} и мы применяем δслучайное ограничение на f, Кроме того, скажем, что дерево решенийT это вычисляет f сжимается до размера O(1)в результате случайного ограничения. Означает ли это, чтоf имеет очень низкое общее влияние?

Амит Леви
источник
δ константа между 0 и 1 и не зависит от n?
Каве
1
Да. Верноδ[0,1],
Амит Леви
1
Я не уверен, что это то, что вы ищете, но по лемме о переключении, если функция может быть представлена ​​DNF малой ширины, тогда она будет сокращена до дерева решений постоянного размера. DNF небольшой ширины имеют низкое суммарное влияние, и деревья решений можно выразить через DNF, поэтому морально кажется, что это так.

Ответы:

4

Претензия: еслиδслучайное ограничение f имеет размер дерева решений O(1) (в ожидании), то общее влияние таких f является O(δ1),

Эскиз доказательства: по определению влияния мы имеем Inf(f)=nPrx,i[f(x)f(x+ei)], Давайте верхнюю границу , сначала применив ограничение, затем выбрав среди оставшихся координат и зафиксировав в случайным образом все, кроме .Prx,i[f(x)f(x+ei)]δi[n]xi

Теперь, если -restrain уменьшает дерево решений до размера , то, в частности, -restrain зависит от скоординированного . Теперь давайте выберем одну случайную нефиксированную координату (среди ) и исправим все остальные случайным образом. Поскольку ограничение зависит не более чем от координат, мы получаем функцию (в один бит), которая не является постоянной с вероятностью не более . Поэтому , как требуется.δfO(1)δfr=O(1)δnδfrrδnInf(f)=nPrx,i[f(x)f(x+ei)]rδ

Примечание: приведенное выше утверждение является строгим, принимая функцию четности для битов.O(1/δ)

Игорь Шинкарь
источник