[cite restrictionmethods.pdf]
Quote from restrictionmethods.pdf slide deck by Benjamin Rossman
Restrictions
The general method of taking a complicated or large problem and performing a random subsample or projection, making the problem easier to understand or solve.
Examples include Johnson-Lindenstrauss lemma for embedding high dimension points into lower dimensions, Monte Carlo sampling for representing probability distributions, and for design of experiments or testing.
Restrictions
- A (random) restriction is a (random) subset R of {0,1}^n - When R is a sub-cube of {0,1}^n, identify with a function {x_1,…,x_n} → {0,1,*} (each coordinate fixed to 0 or 1 or free) - For 0 ≤ p ≤ 1, let R_p denote the p-random restriction Rp(xi) = * with prob. p 0 with prob. (1-p)/2 1 with prob. (1-p)/2
independently for each variable xi