Kitchen Math Hang Su ( Last updated: October 27, 2026) Some Fly by Night TCS and Stuffs Contents 1 Probability and Computing 1.1 Events and Probability 1.2 Discrete Random Variable and Expectation 1.3 Moments and Deviations 1.3.1 Weak Law of Large Numbers (WLLN) 1.4 Chernoff and Hoeffding Bounds 1.4.1 Hoeffding’s Bound 1.4.2 Quicksort Runtime Analysis 1.4.3 Network Routing Problems 1.5 Balls, Bins, and Random Graphs 1.5.1 A few things I should have noted about e 1.5.2 Birthday Paradox and Balls-and-Bins model 1.5.3 Poisson Distribution 1.5.4 Poisson Approximation 1.5.5 Recap on Coupon Collector’s Problem 1.5.6 Hashing and Random Graphs 1.5.7 Hamiltonian Cycles in Random Graphs 1.6 The Probabilistic Method 1.6.1 A few things I should have noted about factorial 1.6.2 Basic Counting Argument 1.6.3 The Expectation Argument and Derandomization by Conditional Expectation 1.6.4 Sample and Modify 1.6.5 The Second Moment Method and the Conditional Expectation Inequality 1.6.6 Lovász Local Lemma 1.6.7 Algorithmic Lovász Local Lemma 1.7 Markov Chains and Random Walks 1.7.1 Stirling’s Formula 1.7.2 Markov Chains and Classification of States 1.7.3 Strong Law of Large Numbers (SLLN) 1.7.4 Stationary Distributions 1.7.5 Random Walks on Undirected Graphs 1.7.6 Parrondo’s Paradox 1.8 Continuous Distributions and the Poisson Process 1.9 The Normal Distribution 1.10 Entropy, Randomness, and Information 1.10.1 The Entropy Function 1.10.2 Entropy and Binomial Coefficients 1.10.3 Entropy: A Measure of Randomness 1.10.4 Entropy: A Limit of Data Compression 1.10.5 Shannon’s Theorem 1.11 The Monte Carlo Method 1.11.1 The Monte Carlo Method 1.11.2 DNF Counting 1.11.3 From Approximate Sampling to Approximate Counting 1.11.4 The Markov Chain Monte Carlo Method (MCMC) 1.12 Coupling of Markov Chains 1.12.1 Variation Distance and Mixing Time 1.12.2 Coupling 1.12.3 Variation Distance is Nonincreasing 1.12.4 Geometric Convergence 1.12.5 Application in Approximately Sampling Proper Colorings 1.12.6 Path Coupling 1.13 Martingales 1.13.1 Martingales 1.13.2 Stopping Times 1.13.3 Wald’s Equation 1.13.4 Azuma-Hoeffding’s Inequality 1.14 Sample Complexity, VC Dimension, and Rademacher Complexity 1.15 Pairwise Independence and Universal Hash Function 1.15.1 Pairwise Independence 1.15.2 Chebyshev’s Inequality for Pairwise Independent Random Variables 1.15.3 Universal Families of Hash Functions 1.15.4 Application in Finding Heavy Hitters in Data Streams 1.16 Power Laws and Related Distributions 1.17 Balanced Allocations and Cuckoo Hashing 2 Pseudorandomness 3 Probabilitic Method 4 Various Papers 4.1 Leftover Hash Lemma and HILL Entropy 4.2 Discrete Gaussian Leftover Hash Lemma 4.3 Schwartz-Zippel by Dana Moshkovitz 4.4 Ligero Interleaved Linear Code Testing 4.5 Interleaved Linear Code Testing with Logarithmic Randomness 4.6 Basefold Random Linear Foldable Code and the Distance Proof 4.7 Bulletproof 4.8 Sublinear Lattice ZKP for Arithmetic Circuits 4.9 A Non-PCP Approach to Succinct Quantum-Safe ZK 4.10 Short Invertible Polynomial Ring Elements 4.11 Lattice-Based Exact Argument of Knowledge 4.12 Practical Product Proof from Lattice Commitments 4.13 Practical Exact Proofs from Lattices 4.14 Lattice Proofs for Exact Euclidean Norm Bounds and Quadratic Relations 4.15 Practical Sublinear Proofs for R1CS from Lattices 4.16 LaBRADOR 4.17 Greyhound 4.18 Lattice-Based Succinct Arguments for NP with Polylog Verification 4.19 Greco References A Degree-Four Bound for Binomial Compression