MathemaTCS

理論計算機科学, 特に平均時計算量(average-case complexity)に関する様々な手法やアルゴリズム, そしてその基となる道具について出来るだけ分かり易く解説していきます. いくつかのページは工事中で未完成ですが, 順次充実させていく予定です.

カバーしている分野

このサイトでは、理論計算機科学の以下の主要分野を体系的に解説しています：

🔬 平均時計算量 (Average-Case Complexity)

• 平均時困難性、Goldreich-Levin定理、直接積定理

📊 情報理論 (Information Theory)

• エントロピー、KLダイバージェンス、相互情報量

🎲 確率論 (Probability Theory)

• 確率集中不等式、統計距離、リード-$k$族

🌐 グラフ理論 (Graph Theory)

• エクスパンダーグラフ、ランダムグラフ、スペクトラルグラフ理論

🎯 ランダムネス (Randomness)

• ランダムネス抽出器、サンプラー、ペア独立性

🔧 誤り訂正符号 (Error-Correcting Codes)

• Reed-Solomon符号、Hadamard符号、リスト復号

🔐 暗号学 (Cryptography)

• Learning with Errors (LWE)、BKWアルゴリズム

📈 高次元統計学 (High-Dimensional Statistics)

• Planted Clique問題、AKSアルゴリズム、Kuceraのアルゴリズム

📐 計算複雑性理論 (Computational Complexity)

• PCP定理、最悪時から平均時への帰着

特徴

• 数学的厳密性: 定義から定理、証明まで体系的に記述
• 直感的理解: 複雑な概念を図解と具体例で説明
• 実用的応用: 理論と実際のアルゴリズム設計の橋渡し
• 相互参照: 関連する概念間のリンクを充実

対象読者

• 理論計算機科学を学ぶ大学院生・研究者
• アルゴリズム設計に興味のあるエンジニア
• 数学的基盤を理解したい実務者
• 計算複雑性理論に興味のある学生

このサイトを通じて、理論計算機科学の美しい理論と実用的な応用の両方を理解していただければ幸いです。