アメリカでは春学期が終わり、私は無事にPhDの一年目を終えました。秋学期の終わりに受けた授業の感想を書いたわけですが、今回も書いてみようと思います。
暗号理論の授業です。試験はなく、隔週の宿題のみで成績が決まるのですが、今までの人生で受けた授業で一番ハードでした。今学期の私の時間はほとんど暗号に消えていました。ちなみに担当の教員は Shafi Goldwasser と Vinod Vaikuntanathan で、暗号理論では著名な二人です。ちなみにMITの暗号理論の研究者といえば他にもたとえばRonald Rivest(RSA暗号の発明者の一人)がいるなど、大物揃いです。(実は私は授業を受けるようになってからそのことを知ったのですが……。)
授業の内容をざっと並べると、
- Perfect Secrecy(Shanon Secrecy)
- Computational Secrecy, One-Way Functions, Hard-Core Predicates
- Discrete Log, RSA, LWE
- Goldreich-Levin Theorem
- Pseudorandom Generators/Function Families
- Trapdoor Functions
- Public Key Encryption
- Zero Knowledge Proofs
- Message Authentication Codes, Digital Signatures
- Collision-Resistant Hash Functions
- Secret Sharing, Oblivious Transfer
- Multi-Party Computation (GMW, Garbled Circuits)
- Fully Homomorphic Encryption
という感じです。とにかく内容が多かった印象です。最初の宿題から難しく、たとえば授業でone-way functionという概念を習うのですが、その具体例をまだ一つも教わっていない状態で「fがone-way functionのとき(fを使って定義された別の関数)もone-way functionであることを示せ」といった問題が沢山出ました。one-way functionを含めこの授業で習う多くの暗号学的な概念は「任意のPPTアルゴリズムに対し、以下が成立する」というようにアルゴリズムが全称量化されて定義されるのですが、そういう命題の証明に今まで慣れていなかったので結構大変でした。私はこの授業で初めてオフィスアワーを頻繁に活用しました。TAの一人は優しくて分かりやすく教えてくれたのでとても助かりました。一方で、zero-knowledge proofs以降のトピックは内容としてかなり面白くて、聞きごたえがありました。
そのまま訳すと「推計と情報」で、推計統計学と情報理論を一緒にやる授業です。成績は、2回の試験と、毎週10ページくらいの宿題(多い！)と、期末プロジェクトで決まります。成績の配分は試験が80%です。これもまたとてもハードでした。試験は3時間あるのですが、3時間あっても足りなそうにしている人がほとんどのように見えました。期末試験の平均点は15/30くらいだったみたいです。
内容は、(ベイズ/非ベイズ)仮説検定、(ベイズ/点)推定、EMアルゴリズム、KL divergence、Fisher情報量、情報幾何(情報理論版ピタゴラスの定理、linear familyとexponential familyの直交性など)、MCMC、漸近理論、などなど。なぜこの授業を取ったかというと情報幾何を学んでみたかったからというのが一番大きいです。
授業内容は聞けば理解できるのですが、試験がめちゃくちゃ難しかったです。試験は授業で習った概念を使いこなすというより、たとえばKL divergenceとは別のdivergenceを定義して、それが凸関数であることや、他にもKL divergenceと比較してどういう性質が成り立つかを示す問題だったりして、どう対策すればよかったのか未だに分かりません。
期末プロジェクトは先生曰く楽しむためのもので、成績の中の配分も5%と低いですが、実際楽しめました。内容はsubstitution cipherを復号する(こっちでも暗号か！)というお題で、私はMetropolis-Hastings法+αで簡単にやっただけでも満点が取れました。
ということで、私はこれらの本当に厳しい(！)授業をなんとかpassして、無事にPhD取得の必要条件の一つである授業のqualificationを終えました。二年目からは研究に集中できそうです。