Notes about TCS

1. Probabilistic Proof Systems

My personal notes of CS294: Foundations of Probabilistic Proofs (F2020) (Alessandro Chiesa)

1.1. Interactive Proofs

Lecture 1: IP#1 - Graph Non-Isomorphism & PSPACE Upper Bound

1.2 Probabilistic Checkable Proofs

Some Basic Facts about PCPs

2. Cryptography

My personal notes of Introduction to Modern Cryptography (Jonathan Katz and Yehuda Lindell)

• Chapter 4: Message Authentication Code

• Chapter 5: Hash Functions and Application

My personal notes of How To Simulate It - A Tutorial on the Simulation Proof Technique(Yehuda Lindell)

• Simulation Proof Technique

3. Analysis of Boolean Function

My personal notes of Analysis of Boolean Function (Ryan O'Donnel)

My personal notes of Advances in Boolean Function Analysis Lecture Series

• On the Fourier-Entropy Influence Conjecture

• Sensitivity Conjecture and It‘s Applications

4. Spectral Graph Theory

My personal notes of Spectral Graph Theory (From the course TCS Toolkits by Ryan O'Donnel)

• Lecture 1: The Quadratic Form and Standard Random Walk
• Lecture 2: The Markov Transition Operator and Laplacian
• Lecture 3: The Sparse-Cut and Mixing Time