ブール関数のスパース性とランクの関係

私は次の定理の証明を通っていたときに次の質問をします。

Theorem. For XOR function $f circ XOR$,
$rank(M_{f circ XOR}) = ||hat f ||_0$ where $M_{f circ XOR}$ is
a matrix such that $M_{f circ XOR}(x,y) = f(x + y)$.

この定理の証明は、$ f $のフーリエ係数が$ M $:$
の固有値であることを本質的に示している。f(S)$は固有値であり、対応する固有ベクトルは$ chi_S
$である。そして今、スペクトル分解を使用して、ランクがスパース性に等しいと結論付けることができる。


My question is: Consider any function
$F:{0,1}^N rightarrow {0,1}$, and let $M_F in {0,1}^{N/2}
times {0,1}^{N/2}$ be a $2^{N/2} times 2^{N/2}$ dimensional
matrix whose entries are as follows: $$M_F(x,y) = F(xy).$$ Is there
any relationship between $||hat F||_0$ and $rank(M_F)$?

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です