アルゴリズム特論IV（ブール関数の解析）

ブール関数の解析手法の基礎を学習する．一般に，連続的な数学的対象物と離散的なそれとでは解析手法が異なる．連続的な数学的対象物で有効であった解析手法が，離散的なそれには全く効かないことがよく生じる．（ランダム行列や凸解析など．）ここでは，連続関数の典型的な解析手法であるフーリエ解析が，離散的な関数であるブール関数へ適用された場合，実際，どのような概念及び解析手法が開発されたのか，理論計算機科学で発見された代表的な定理を通して学習する．

テキスト

講義スケジュール 

1. 導入（ブール関数とその解析手法）

2. 離散フーリエ解析（離散フーリエ解析の基礎）

3. BLR の定理（Blum-Luby-Rubinfeld の線形性テスト）

4. Influence

5. Noise Stability

6. Noise Sensitivity

7. Arrow の定理（社会選択理論における Arrow の定理）

8. フーリエスペクトル

9. Restriction

10. 低次関数のフーリエスペクトル

11. GL の定理（Goldreich-Levin の定理）

12. Random Restriction

13. DNF 論理式のフーリエスペクトル

14. LMN の定理（Linial-Mansour-Nisan の定理）

Last Update: 02/April/2025