Булевы функции, где чувствительность равна блочной чувствительности

17

Некоторая работа по чувствительности против чувствительности блоков была направлена ​​на изучение функций с максимально большим промежутком между и , чтобы развить гипотезу, что только полиномиально больше, чем . Как насчет противоположного направления? Что известно о функциях, где ?s(f)bs(f)bs(f)s(f)s(f)=bs(f)

Тривиально, постоянные функции имеют . Также тривиально, любая функция с также имеет . Нетривиально, но не слишком сложно показать, что любая монотонная функция также удовлетворяет этому равенству. Есть ли другие хорошие классы функций, которые имеют ? Полная характеристика была бы идеальной. Что если мы еще больше усилим требования к и ?0=s(f)=bs(f)s(f)=ns(f)=bs(f)s(f)=bs(f)s0(f)=bs0(f)s1(f)=bs1(f)

Мотивация для этого вопроса - просто понять, как чувствительность связана с чувствительностью блока.

Определения

Пусть - булева функция на битных словах. Для и , пусть х Обозначим п -битовый слово , полученное из х , переворачивая биты , установленные А . В случае, когда A = { i } , мы просто обозначим это как x i .f:{0,1}n{0,1}nx{0,1}nA{0,1,,n}xAnxAA={i}xi

Определим чувствительность f в x как s(f,x)=#{i|f(xi)f(x)} . Другими словами, это число бит в которое мы можем перевернуть, чтобы перевернуть вывод . Определим чувствительность от как . xffs(f)=maxxs(f,x)

Мы определяем чувствительность блока вfx (обозначается как ) как максимум такой, что существуют непересекающиеся подмножества из такие что . Определим чувствительность блока из , как .bs(f,x)kB1,B2,,Bk{1,2,,n}f(xBi)f(x)fbs(f)=maxxbs(f,x)

Наконец, мы определяем 0 чувствительность по f как s0(f)=max{s(f,x)|f(x)=0} . Аналогичным образом мы определяем 1-чувствительность , 0-блоковую чувствительность и 1-блоковую чувствительность , обозначаемую s1(f) , bs0(f) и bs1(f) соответственно.

mhum
источник

Ответы:

17

Недавно я доказал, что s (f) = bs (f) для функций unate и функций однократного чтения над булевыми операторами AND, OR и EXOR, и моя статья, включая результаты, была принята в TCS 2014. ( http: // dx .doi.org / 10.1007 / 978-3-662-44602-7_9 )

Вы можете атаковать эту проблему. Если так, мне жаль, но я начал атаковать проблему самостоятельно, прежде чем вопрос был опубликован. Предварительная версия моей статьи была представлена ​​на внутреннем совещании в Японии в декабре 2013 года, а крайний срок представления был октябрь 2013 года. ( http://www.ieice.org/ken/paper/20131220DBID/eng/ )

Хироки Морицуми
источник
2
Хороший результат. Я с нетерпением жду, чтобы прочитать это.
mhum