Boolesche Funktionen, bei denen die Empfindlichkeit der Blockempfindlichkeit entspricht

Einige der Arbeiten zur Empfindlichkeit im Vergleich zur Blockempfindlichkeit zielten darauf ab, Funktionen mit einer möglichst großen Lücke zwischen $s(f)$ und $bs(f)$ zu untersuchen, um die Vermutung aufzulösen, dass $bs(f)$ nur polynomiell größer ist als $s(f)$ . Was ist mit der Gegenrichtung? Was ist über Funktionen mit $s(f) = bs(f)$ ?

Trivialerweise haben konstante Funktionen $0=s(f)=bs(f)$ . Ebenfalls trivialerweise hat jede Funktion mit $s(f) = n$ auch $s(f) = bs(f)$ . Es ist nicht trivial, aber nicht zu schwer zu zeigen, dass jede monotone Funktion auch diese Gleichheit erfüllt. Gibt es andere nette Klassen von Funktionen, die $s(f) = bs(f)$? Eine vollständige Charakterisierung wäre ideal. Was ist, wenn wir die Anforderungen an $s^0(f) = bs^0(f)$ und $s^1(f) = bs^1(f)$ ?

Die Motivation für diese Frage besteht einfach darin, sich ein Bild davon zu machen, wie die Empfindlichkeit mit der Blockempfindlichkeit zusammenhängt.

Definitionen

Sei $f:\{0,1\}^n\rightarrow \{0,1\}$ eine Boolesche Funktion für $n$ Bit-Wörter. Für $x \in \{0,1\}^n$ und $A \subseteq \{0,1,\ldots,n\}$ bezeichne $x^A$ das $n$ Bit-Wort, das aus $x$ durch Spiegeln der durch $A$ angegebenen Bits erhalten wird . Für den Fall, dass $A = \{i\}$ , wir bezeichnen dies einfach als$x^i$ .

Wir definieren die Empfindlichkeit von $f$ bei $x$ als $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$ . Mit anderen Worten, es ist die Anzahl der Bits in $x$ , die wir kippen können, um die Ausgabe von $f$ zu kippen . Wir definieren die Empfindlichkeit von $f$ als $s(f) = \text{max}_x s(f,x)$.

Wir definieren die Blockempfindlichkeit von $f$ bei $x$ (bezeichnet mit $bs(f,x)$ ) als das Maximum $k$ so dass disjunkte Teilmengen $B_1, B_2, \ldots, B_k$ von $\{1,2,\ldots, n\}$ wie z daß $f(x^{B_i}) \neq f(x)$ . Wir definieren die Blockempfindlichkeit von$f$ als$bs(f) = \text{max}_x bs(f,x)$ .

Schließlich definieren wir die 0-Empfindlichkeit von $f$ als $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$ . Wir definieren in ähnlicher Weise 1-Empfindlichkeit , 0-Block-Empfindlichkeit und 1-Block-Empfindlichkeit , bezeichnet mit $s^1(f)$ , $bs^0(f)$ und $bs^1(f)$ jeweils.

Kürzlich habe ich bewiesen, dass s (f) = bs (f) für Unate-Funktionen und Read-Once-Funktionen über die Booleschen Operatoren AND, OR und EXOR gilt, und meine Arbeit einschließlich der Ergebnisse wurde in TCS 2014 aufgenommen. ( Http: // dx .doi.org / 10.1007 / 978-3-662-44602-7_9 )

Möglicherweise greifen Sie dieses Problem an. Wenn ja, tut es mir leid, aber ich habe begonnen, das Problem selbständig anzugreifen, bevor die Frage veröffentlicht wurde. Eine vorläufige Version meines Papiers wurde auf einem japanischen Inlandstreffen im Dezember 2013 vorgestellt und die Einreichungsfrist war Oktober 2013. ( http://www.ieice.org/ken/paper/20131220DBID/eng/ )