海外生活日記: sensitivity conjecture

1年前のことらしいのですが、

chromeのフィードに関連記事がおすすめとして出てきて面白かったので、ここに共有。

30年間コンピューターサイエンティストが解けなかった問題が、とある数学者による2枚弱の論文によって証明された。というもの。

記事を読むと、どうやらそんなに難しくないらしい。ということで実際に読んでみると

学部の知識で理解できるし、流れもエレガント！これ気持ちいいだろうな、と想像笑

実際の問題というのが、sensitivity conjecture(敏感度予想)というもの。（専門用語の訳は適当）

sensitivityというのは、n次元のインプットに対するブール関数 f:{0,1}^n->{0,1}について、

x\in{0,1}^n, S\subset[n]={1,2,...,n}について、x^SをSに対応するxの要素を０と１で入れ替えたものとすると、

local sensitivity:　s(f,x)=number of i such that f(x)≠f(x^i)

sensitivity:　max{s(f,x): x\in{0,1}^n}

local block sensitivity:　bs(f,x) = maximum number of disjoint blocks B1, B2, ...Bk\subset[n] such that f(x)≠f(x^Bi) for all i

block sensitivity:　max{bs(f,x):x\in{0,1}^n}

Sensitivity conjecture: there exists an absolute constant C such that for every boolean function f, bs(f)<=s(f)^C

これを、

n次元の超立方体グラフQ^nの（2^(n-1)+1）の頂点を持ついかなるサブグラフHも、最大次数がｎの平方根より大きい

ということを証明することで導いている。固有値などの基本的な議論。わずか１ページ半。しびれる。

下参考。

海外生活日記