Libx Awesomeリスト

    このページの内容

    Awesome Theoretical Computer Science

    Theoretical Computer Scienceを扱う資料や関連プロジェクトをまとめたAwesomeリストです。

    目次

    概説

    講義ノート

    講義動画プレイリスト

    書籍

    ハンドブック

    計算理論

    入門

    講義ノート

    MOOC

    • Intro to Theoretical Computer Science - 理論的コンピュータサイエンスにおける基本的な概念、例えばNP完全性、そしてそれらが困難なアルゴリズ及問題の解決にどう影響するかを教えている。
    • Computability, Complexity & Algorithms. Georgia Institute of Technology - 計算の大きな基本的な問いに焦点を当て、アルゴリズムの力と限界を理解することで、現実のコンピュータを賢く、速く、安全に設計するためのツールを構築できるようになることを説明する。

    書籍

    パズルと問題集

    計算複雑性

    入門

    講義動画プレイリスト

    講義ノート

    • Rudich & Wigderson. Computational Complexity Theory - IAS/パーキー・シティ・マスティクス・インスティテュートの夏学校で行われた計算複雑性に関する3週間の講義。テーマには、帰約、下限、平均ケース複雑性、ランダム性、インタラクティブプローフシステム、確率的にチェック可能な証明、量子コンピューティング、および証明複雑性が含まれる。

    書籍

    大規模リスト

    • Complexity Zoo - 計算理論の資料を集約したリソース。

    通信複雑性

    講義ノート

    • Mark Bun. CS591 Communication Complexity - 研究生向けのコースで、この分野の基本的な成果と技術、および一部の研究の先端的な問題を紹介。テーマには、通信モデルと通信複雑性のゾーン、情報と通信、クエリから通信への昇格、および応用がある。

    書籍

    回路複雑性

    書籍

    量子複雑性

    講義動画プレイリスト

    講義ノート

    証明複雑性

    講義ノート

    計算可能性理論

    書籍

    入門

    上級

    モノグラフ

    論理学

    計算複雑性

    書籍

    プログラミング言語理論

    基礎

    講義ノート

    • Cambridge Foundations of CS - プログラミングを教えるとともに、コンピュータサイエンスのいくつかの基本原則、特にアルゴリズム設計を紹介する。

    書籍

    入門

    書籍

    • Pierce. Software Foundations. Pennsylvania - 信頼性のあるソフトウェアの数学的根拠についての広範な導入シリーズ。これは、Coq証明補助システムの証明スクリプトから構成されている。特定のバックグラウンドを仮定せず、幅広い読者に向けられている。

    形式検証

    講義ノート

    • UW CSE505 18au Principles of PL - プログラミング言語について鋭く考えるための技術、いくつかの興味深いプログラムを書くこと、そしてさまざまな設計のトレードオフについて議論する。

    書籍

    型理論

    講義ノート

    書籍

    関数型プログラミング

    講義ノート

    • Helsinki. Haskell MOOC - Haskellプログラミング言語を使った関数型プログラミングのオンラインコースおよびライブインタラクティブなTelegramコミュニティ。
    • Cornell. Functional Programming in Ocaml - OCamlを用いたデータ構造と関数型プログラミングの現代的なコース。

    アルゴリズム

    一般

    講義動画

    講義ノート

    • Arora. Advanced Algorithm Design - 特にランダム性、近似、高次元幾何学といった考え方が使われており、不確実性を扱い、大規模データの処理、解けない問題の扱い、ヒューリスティックなアプローチなどについて述べている。

    書籍

    下界

    講義動画プレイリスト

    書籍

    • Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds - ゲリーとジョンソンの『コンピュータと非解不可能性：NP完全性へのガイド』の続編。新たに取り上げたトピックには、パラメータ化複雑性、近似の下限、他のハードネス仮定（ETH、3SUM予想、APSP予想、UGC、その他）、オンラインアルゴリズム、ストリーミングアルゴリズ、多項式パリティ論理、並列性などが含まれる。
    • Demaine. Games, Puzzles, and Computation - ゲームやパズルが計算モデルとして強力な手段であることを示しており、計算についての新たな考え方が提供されている。

    ランダム化と確率

    講義ノート

    • Mary Wootters. Randomized Algorithms and Probabilistic Analysis. Stanford - 確率解析の基本的なツールと、それらを用いてランダムプロセスやアルゴリズムの行動を理解するための応用。理論的基礎に重点を置いているが、機械学習やデータ分析、ネットワーク、システムにおける応用についても述べる。テーマには、尾の境界、確率的手法、マーカーチェーン、マーティンゲル、ランダムグラフ、メトリック埋め込み、ランダムウォークの解析などがある。
    • Koutsoupias. Probability and Computing. Oxford - コンピュータサイエンスにおける確率的手法の紹介。
    • Harvey. First and Second Course in Randomized Algorithms. Columbia. - アルゴリズム理論を学ぶための講義ノート。
    • Lee. Randomized Algorithms and Probabilistic Analysis. Washington. - テーマには、離散確率、高次元幾何学と統計、情報とエントロピー、マーカーチェーンと均衡への収束がある。
    • Aspnes. Notes on Randomized Algorithms - ミツネマッハァー＆アップファルス、およびモトワニ＆ラグヴァンの標準書への補足ノート。

    近似

    講義ノート

    書籍

    パラメータ化

    講義動画プレイリスト

    書籍

    • Fedor Fomin. Parametrized Algorithms - Modern comprehensive explanation of recent tools and techniques with exercises, for graduate students.

    学習拡張

    講義ノート

    大規模リスト

    情報理論・符号理論

    講義ノート

    暗号理論

    書籍

    機械学習理論

    講義ノート

    • Blum. An Introduction to the Theory of Machine Learning. TTIC - 機械学習の基本理論およびデータから一般化するプロセス。
    • Telgarsky. Deep Learning Theory. Illinois - 単純な証明に焦点を当て、文献に記載されている内容を簡略化し、i.i.d.データ上で二値分類において低テスト誤差を達成するための標準（通常はReLU）の前向きネットワークの古典的アプローチを扱う。
    • Vaughan. CS260: Machine Learning Theory - 一般的な機械学習アルゴリズムの理論的基礎に関する包括的な概観。
    • Livni. COS 511 Theoretical Machine Learning. Princeton - 学習モデルとして提案されたさまざまなモデルを形式的に定義し、研究する。本講義では、統計的、計算的およびオンライン学習モデルを提示し、比較する。また、今日までに広く使用されている機械学習における最も成功したアルゴリズムのいくつかを提示し、厳密に分析する。
    • Moitra. Theoretical Foundations for Deep Learning. MIT - 深層学習の理論的基礎を探索し、以下のテーマに焦点を当てる：(1) 近似：深層ネットワークが表現できる関数の種類は何か、そして深層が表現力の向上を確実に保証するか？(2) 最適化：実際の問題で解決したいすべての最適化問題は非凸である。このような問題を分析するためのフレームワークは何か？(3) 最悪ケース分析を超える：深層ネットワークは最悪ケースデータを記憶できるが、なぜ現実世界のデータ上で良好な一般化が可能なのか？
    • Arora. Overcoming Intractability in Machine Learning - 機械学習における多くの問題は形式的に計算不可能（例：NP困難）であるが、実際にはヒューリスティックによって解決される。このような問題に対して、証明可能な保証（実行時間、解の品質）を持つアルゴリズムを設計できるか？

    書籍

    その他

    ゲーム理論

    講義ノート

    • Tim Roughgarden. Complexity Theory, Game Theory, and Economics: The Barbados Lectures - 二重目的を持つミニコースノート：(i) 複雑性理論が経済学およびゲーム理論におけるいくつかの障壁を明らかにした方法を説明する；(ii) ゲーム理論の問題が新しいかつ興味深い複雑性理論（特に最近のいくつかの突破）を生み出した方法を示す。
    • Eva Tardos. Algorithmic Game Theory - アルゴリズ及的思考とゲーム理論、あるいはより一般的に経済学の概念を組み合わせる。本講義では、この交差点におけるさまざまなテーマを研究する。講義の前提知識は数学的思考のみである。
    • Chekuri. Topics in Algorithms: Algorithmic Game Theory - 大学院レベルの概説：オークション、ゲームおよび市場における均衡の存在と計算、アルゴリズムメカニズム設計、アンarchyの価格と安定の価格、ネットワークおよび電子商取引に関連するゲーム。重点は概念的アイデアおよびアルゴリズム的側面にある。ゲーム理論や経済学の知識は前提として求められない。
    • Penna. Algorithmic Game Theory - 本講義では、ゲーム理論のアルゴリズム的側面について議論する。例えば、ゲーム理論の一般導入、オークション、メカニズム、中央制御の最適解と自発的代理者の均衡のコストの比較、および均衡を計算するアルゴリズムと複雑性について。
    • Brown. Resources list for game theory - これらのノートは、スタンフォード大学のティム・ラウガーデンのCS 364AおよびCS 364B講義ノートおよび関連動画、およびジェイソン・ハートラインの「メカニズム設計と近似」教科書に基づいて largely 作成された。
    • Fang. Advanced Topics in Machine Learning and Game Theory - Fangによる、機械学習とゲーム理論の交差領域を扱う大学院レベルの講義です。
    • Xu. Topics in Learning and Game Theory - Xuによる、機械学習とゲーム理論の接点にあるトピックを扱う大学院レベルの講義です。
    • Tim Roughgarden. Foundations of Blockchains - ゲーム理論を学ぶための講義ノート。 関連資料: Lecture Videos。

    書籍

    • Apt & Grädel. Lectures in Game Theory for Computer Scientists - ゲームは相互作用のための数学的モデルであり、コンピュータサイエンスの多くのタスクはゲーム理論の観点から表現できる。
    • Eva Tardos & et.al. Algorithmic Game Theory - 均衡、メカニズム設計および組合せオークションのためのアルゴリズム的手法に関する基本的な章を経て、インセンティブおよび価格、コスト共有、情報市場および暗号・セキュリティといったゲーム理論の重要な応用に関する章へと続く。

    数学と論理

    一般

    講義動画プレイリスト

    書籍

    講義ノート

    理論計算機科学の道具箱

    講義動画プレイリスト

    講義ノート

    書籍

    • Jukna. Extremal Combinatorics - 理論的コンピュータサイエンスにおける応用を意識した組合せ的手法を記述。主に複雑性に焦点を当てる

    離散数学

    一般

    講義ノート

    書籍

    MOOC

    確率的方法

    講義ノート

    講義動画プレイリスト

    書籍

    グラフ理論

    講義動画プレイリスト

    その他

    物理学

    講義ノート

    書籍

    モノグラフ

    哲学

    講義ノート

    書籍

    論文

    サーベイとモノグラフ

    コミュニティ

    会議とワークショップ

    集約サイト

    開催中

    • Simons’ Institute - 理論コンピュータサイエンスコミュニティ全体にわたって影響力と参加を最大化するためのプログラム、イベント、ワークショップ
    • TCS+ - 理論コンピ連絡のオンラインセミナー。目標は、可能な限り広い層に魅力的な講演を提供すること
    • CMU Theory - コンピュータサイエンスにおける基本的な問題についての数学的解釈を目指し、その理解をもとにより優れたアルゴリズム、プロトコル、システムを設計し、効率的な計算の内在的な制限を明らかにする。

    アーカイブ

    雑誌とニュースレター

    • EATCS Bulletin - 調査、チュートリアル、会議報告、イベント、未解決問題とその解決策、博士論文、そして興味深い寄稿。
    • SIGACT News - ACMの公式な理論コンピュータサイエンスニュースフィード。
    • Foundations and Trends in Theoretical Computer Science - 論文に掲載されるのは、理論のリーダーが執筆した単著で、テーマのチュートリアル的解説、研究の振り返り、および最先端の調査論文が該当する。
    • Quanta Magazine - 分野における突破的な成果を、専門家でない読者にも理解しやすいスタイルで記述。

    学会・団体

    ブログ

    集約サイト

    厳選記事・エッセイ

    求人

    オンラインコミュニティ

    • TCS Stack Exchange - 理論計算機科学コミュニティについて交流できるオンラインコミュニティ。
    • TCS Subreddit- 理論計算機科学のSubreddit。

    その他

    ポッドキャスト

    一般向け科学

    チートシート

    関連リスト