The big ideas of computer science, with the fine print

Statement

With one uniformly random choice per ball, the maximum load $L_1$ satisfies, with high probability,

while letting each ball join the least loaded of $d\ge2$ independent random bins (Greedy[$d$]) gives

With $m\gg n$ balls the one-choice gap above the mean grows like $\sqrt{(m/n)\ln n}$, while the $d$-choice gap stays $\ln\ln n/\ln d+O(1)$, independent of $m$.

Why it's true

One choice: $\Pr[\text{a given bin gets}\ge k]\le\binom nk n^{-k}\le 1/k!$, and a union bound over $n$ bins is below 1 once $k!>n$, i.e. $k\approx\ln n/\ln\ln n$. A matching second-moment argument gives the lower bound. Two choices, by layered induction: let $\beta_i$ bound the number of bins with load $\ge i$. A ball lands at height $i+1$ only if both its choices already have load $\ge i$, which happens with probability $(\beta_i/n)^2$. So $\beta_{i+1}\lesssim n(\beta_i/n)^2$, and the fraction squares at every level. Doubly exponential decay reaches $1/n$ after $\log_2\ln n$ levels.

Statement

A cache holds $k$ pages. Offline, MIN (evict the page whose next request is furthest in the future) minimizes faults (Bélády, 1966). An online algorithm $A$ is $c$-competitive if $\mathrm{cost}_A(\sigma)\le c\cdot\mathrm{OPT}(\sigma)+b$ for every request sequence $\sigma$. Sleator and Tarjan proved:

so with equal caches LRU and FIFO are $k$-competitive, and no deterministic algorithm does better. Randomized marking is $2H_k$-competitive against an oblivious adversary, and $H_k\approx\ln k$ is a lower bound (Fiat et al., 1991).

Why it's true

Lower bound: use $k+1$ distinct pages and always request the one the online algorithm doesn't hold. It faults on every request. MIN, on a fault, evicts the page needed furthest ahead, so it faults at most once per $k$ requests. Upper bound for LRU: split $\sigma$ into phases of $k$ distinct pages. LRU faults at most $k$ times per phase, and OPT must fault at least once per phase boundary.

Statement

Let $F$ have $n$ variables and $m=\alpha n$ clauses, each with 3 distinct variables chosen uniformly and negated independently with probability $\tfrac12$. Friedgut (1999) proved the transition is sharp: there is $\alpha_c(n)$ such that for any $\epsilon>0$, $\Pr[F\text{ sat}]\to1$ for $\alpha<(1-\epsilon)\alpha_c(n)$ and $\to0$ above $(1+\epsilon)\alpha_c(n)$. Statistical physics predicts $\alpha_c\approx4.267$ (Mézard, Parisi & Zecchina, 2002). For $k=3$ the proven bounds are about $3.52\le\alpha_c\le4.49$, and the exact value is established only for large $k$ (Ding, Sly & Sun, 2015).

Why it's true

First moment: a fixed assignment satisfies a random clause with probability $7/8$, so

and Markov's inequality gives unsatisfiability. The true threshold is lower because solutions are highly correlated, so the expectation is dominated by rare formulas with many solutions. For the hardness peak, below $\alpha_c$ there are many solutions and backtracking stumbles on one. Above it, contradictions appear after a few decisions, so refutation trees shrink as $\alpha$ grows. At the threshold the search must explore deep and wide (Cheeseman, Kanefsky & Taylor, 1991; Mitchell, Selman & Levesque, 1992).

Statement

Hash each item to a uniform bit string. The first $b$ bits pick one of $m=2^b$ registers, and register $j$ keeps $M_j=\max\rho$, where $\rho$ is the position of the first 1 in the remaining bits. The estimate is

with relative standard error

For small $n$, if $E\le\tfrac52m$ and $V>0$ registers are still zero, use linear counting, $m\ln(m/V)$, instead.

Why it's true

$\Pr[\rho\ge r]=2^{-(r-1)}$, so among $n/m$ items in a register the maximum $\rho$ sits near $\log_2(n/m)$, and $2^{M_j}$ estimates $n/m$ up to a constant. One register has huge variance. Stochastic averaging over $m$ registers, using the harmonic mean to blunt the occasional very large $M_j$, gives the $1/\sqrt m$ rate, and $\alpha_m$ removes the multiplicative bias. Registers hold values up to about $\log_2\log_2 n$ bits wide, hence "LogLog."

Statement

For the $\mathrm{BSC}(p)$, with $H_2(p)=-p\log_2p-(1-p)\log_2(1-p)$,

For every rate $R<C$ there are codes of length $n$ and rate $R$ with block error probability $\to0$ as $n\to\infty$. For $R>C$ the error probability is bounded away from zero (strong converse: it tends to 1).

Why it's true

Achievability by random coding: draw $2^{nR}$ codewords uniformly. The channel flips about $np$ bits, so the received word lies in a Hamming ball of about $2^{nH_2(p)}$ points around the sent codeword. The whole space has $2^n$ points, so you can pack about $2^{n(1-H_2(p))}$ nearly disjoint balls, and a random codebook does so with high probability. Averaging over codebooks shows that some fixed codebook works. The converse follows from Fano's inequality: $nR\le I(X^n;Y^n)+1+P_e nR\le nC+1+P_e nR$.

Statement

An interactive proof $(P,V)$ for a language $L$ is complete (honest $P$ convinces $V$ on $x\in L$), sound (on $x\notin L$ any prover succeeds with probability $\le s$) and zero-knowledge (there is a simulator $S$ that, for any efficient verifier $V^*$, outputs transcripts indistinguishable from real interactions). Goldreich, Micali and Wigderson showed that every language in NP has a computational zero-knowledge proof if one-way functions exist, via graph 3-colouring. In each round:

A prover without a valid colouring is caught with probability $\ge1/|E|$ per round, so after $t$ independent rounds it survives with probability at most $(1-1/|E|)^t\le e^{-t/|E|}$.

Why it's true

Soundness: binding commitments fix a colouring before the challenge, and an invalid colouring has at least one bad edge. Zero knowledge: for a valid colouring, the two opened colours are a uniformly random ordered pair of distinct colours, whatever the edge. The simulator guesses the challenge edge in advance, commits to two random distinct colours on it (and anything on other vertices), and rewinds $V^*$ when its guess is wrong. Hiding commitments make the unopened vertices indistinguishable.

Statement

Fischer, Lynch and Paterson (1985): in the asynchronous message-passing model with reliable links, no deterministic protocol for binary consensus satisfies agreement, validity and termination if one process may fail by crashing. Under partial synchrony, where message delays are eventually bounded, consensus is solvable with $f<n/2$ crash failures (Dwork, Lynch & Stockmeyer, 1988). With randomization it terminates with probability 1 (Ben-Or, 1983).

Why it's true

A configuration is bivalent if both decisions are still reachable. Validity and the possibility of one crash give a bivalent initial configuration. Then, for any pending message $e$, the set of configurations reachable by delivering $e$ last contains a bivalent one. Otherwise two neighbouring configurations would decide differently, depending only on one process's step, and crashing that process makes them indistinguishable. The adversarial scheduler can therefore keep the system bivalent forever. Raft escapes by electing a leader. Each follower times out after $T+U$, with $U\sim\mathrm{Unif}[0,W]$, and the first to time out usually collects a majority before anyone else starts. For $n$ followers, the gap between the two earliest timeouts exceeds $\delta$ with probability $(1-\delta/W)^n$.

Statement

Gifford's weighted voting (1979): if $R+W>N$, any $R$-set and any $W$-set intersect, so a read sees the latest acknowledged write (for a single register, no concurrent writes). For partial quorums ($R+W\le N$), if the read contacts a uniformly random $R$-set immediately after the write is acknowledged by exactly $W$ replicas,

and the probability falls with time $t$ after commit as the remaining replicas receive the write (probabilistically bounded staleness, Bailis et al., 2012).

Why it's true

Pigeonhole: $|R\cap W|\ge R+W-N\ge1$. For partial quorums, the read misses the write only if all $R$ replicas it contacts come from the $N-W$ that haven't yet applied it, which is a hypergeometric count. For $t>0$ each straggler has independently applied the write with probability $F(t)$, its delay distribution, so the bound improves at the rate of that distribution's tail.

Statement

If leaf latencies $X_1,\dots,X_k$ are i.i.d. with CDF $F$ and the request waits for all of them, its latency $\max_iX_i$ has CDF $F^k$, so

so the $q$-quantile of the request latency is $F^{-1}\!\left(q^{1/k}\right)$.

With a hedge sent after delay $h$ to an independent replica, each leaf's latency becomes $\min(X,\,h+X')$.

Why it's true

Independence makes the max's CDF a product. With $1-F(x)=0.01$ and $k=100$, $1-0.99^{100}\approx0.63$. The $p99$ of the request is the $0.99^{1/100}\approx p99.99$ of a leaf, so fan-out moves the quantile you care about deep into the leaf's tail. Hedging after $h$ at the leaf's $p95$ adds about 5% load. A leaf is still slow only if both copies are slow, which under independence squares the tail probability.

Statement

Take $n$ samples, $p$ features and the minimum-norm least-squares fit $\hat\beta=X^{+}y$. For isotropic Gaussian features in the proportional limit $p/n\to\gamma$, with signal strength $r^2=\|\beta\|^2$ and noise variance $\sigma^2$, the excess test risk is (Hastie, Montanari, Rosset & Tibshirani, 2022)

which diverges at $\gamma=1$. Similar curves appear for random-feature models, kernels and deep networks as width, training time or data size varies (Belkin et al., 2019; Nakkiran et al., 2020).

Why it's true

The variance term is $\sigma^2\operatorname{tr}\big((X^\top X)^{+}\big)$ up to scaling. By Marchenko–Pastur, the smallest nonzero singular value of $X/\sqrt n$ is about $|1-\sqrt\gamma|$, which vanishes at $\gamma=1$, so a square design inverts tiny singular values and amplifies the noise. For $\gamma>1$, many interpolating solutions exist. The minimum-norm one spreads the fit over many directions, the smallest singular value grows again, and variance falls like $1/(\gamma-1)$. Bias rises because the fit lives in an $n$-dimensional subspace of a $p$-dimensional space.

Statement

A randomized mechanism $M$ is $\varepsilon$-differentially private if, for all datasets $D,D'$ differing in one record and all output sets $S$,

The Laplace mechanism releases $f(D)+\mathrm{Lap}(\Delta f/\varepsilon)$, where $\Delta f=\max|f(D)-f(D')|$. Running mechanisms with budgets $\varepsilon_1,\dots,\varepsilon_k$ is $(\sum\varepsilon_i)$-DP (basic composition), and $k$ runs at $\varepsilon$ each are $(\varepsilon\sqrt{2k\ln(1/\delta)}+k\varepsilon(e^\varepsilon-1),\,\delta)$-DP (advanced composition).

Why it's true

The Laplace density is proportional to $e^{-|z-\mu|\varepsilon/\Delta f}$. Moving the centre by at most $\Delta f$ changes the density at every point by a factor of at most $e^{\varepsilon}$, and integrating gives the bound for any $S$. For composition, the likelihood ratios multiply, so the log-ratios add. Consequence: with equal priors, no test can distinguish $D$ from $D'$ with accuracy above $e^{\varepsilon}/(1+e^{\varepsilon})$.

Statement

Let a comparison of guess $g$ against secret $s\in\Sigma^L$ take time $T(g)=c_0+\Delta\cdot\mathrm{lcp}(g,s)+\eta$, with $\eta$ noise of standard deviation $\sigma$. Recovering $s$ character by character needs

queries, with $N$ samples per candidate, instead of $|\Sigma|^L$ for brute force.

Why it's true

At each position the right candidate takes $\Delta$ longer than the $|\Sigma|-1$ wrong ones. Averaging $N$ samples shrinks the noise to $\sigma/\sqrt N$, so picking the largest mean is a multiple-comparison test whose error falls exponentially in $N\Delta^2/\sigma^2$. Random delays only increase $\sigma$, which the attacker offsets with more samples. Constant-time comparison (accumulate $\bigvee_i(g_i\oplus s_i)$ over all positions with no data-dependent branch) makes $\Delta=0$ and the signal disappears.