集中講義　性質検査

京都大学大学院理学研究科数学・数理解析専攻数理解析系 数理解析特別講義１ 計算機科学（集中講義）

• 日　時：２０１４年７月１４日（月）・１５日（火）・１６日（水）・１７日（木） １４時～
• 場所：数理解析研究所１階 111号室

内容

ある性質を「判定する」とは、入力がその性質を満たすか、満たさないかを区別することである。それに対してある性質を「検査する」とは、入力 がその性質を満たすか、入力を満たすには「ほど遠いか」を区別することを指す。この様に問題を緩和することで、多くの問題が定数時間、即ち入力の大きさに依らない時間で検査できるようになることが知られている。

性質検査は理論計算機科学の様々な分野と関連しており、その理論はこの20年で劇的に進歩した。特に幾つかの設定では、定数時間で検査できる 性質の特徴付けも得られている。 本講義では、性質検査の中で特に成功しているグラフとブーリアン関数の検査を取り扱う。幾つかの重要な性質の検査と、それらを用いてどの様に して定数時間で検査可能な性質の特徴付けが得られたかを解説する。

• 性質検査とは？
• グラフの性質検査
  • 二部性の検査
  • Szemerédiの正則性補題とTriangle-freeness
  • 正則性に基づく検査可能な性質の特徴付け
• ブール関数の性質検査
  • 線形性の検査
  • Greenの正則性補題とTriangle-freeness
  • 下限の証明手法（Yao’s minimax lemmaと通信複雑性）
  • 正則性に基づく検査可能な性質の特徴付け