ブール関数のsensitivity, block sensitivity, certificate complexity について
スポンサーリンク
概要
- 論文の詳細を見る
本論文では、ブール関数のsensitivity, block sensitivity, certificate complexity に関して成立する関係をいくつか示す。任意のn変数ブール関数のsensitivity s≥2とcertificate complexity c についてc≤2^<s-1>s-1が成立することを示す。また、sensitivity s, certificate complexity cの n変数ブールが存在すれば、s≤S′≤c′≤cを満たす任意のsとcについて、sensitivity s′, certificate complexity c′のn変数ブール関数が存在することを示す。得られた関係により、n≤7の場合の(n, s, c)のとりうる値を完全に決定することができる。
- 1998-03-24
著者
関連論文
- [チュートリアル講演]最小値独立置換族に関する最近の成果
- 最小値独立置換族に関する最近の成果
- 有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成
- k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界
- 置換族とその独立性の解析
- 集中討論:DeolalikarのP≠NP論文をめぐって
- 否定数限定論理回路におけるマージングの複雑さ
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- あるノイズモデルにおけるブール関数学習について
- フェイステル変換を用いた近似的k-対ランダム置換族の構成
- kトニックな0/1列に対する線形サイズ対数深さの否定数限定インバータ
- ブール関数のsensitivity, block sensitivity, certificate complexity について
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 計算の複雑さと証明の複雑さ : 基調講演 (証明論と複雑性)