$\require{mathtools}
%
%%% GENERIC MATH %%%
%
% Environments
\newcommand{\al}[1]{\begin{align}#1\end{align}} % need this for \tag{} to work
\renewcommand{\r}{\mathrm}
%
% Greek
\newcommand{\eps}{\epsilon}
\newcommand{\veps}{\varepsilon}
\let\fi\phi % because it looks like an f
\let\phi\varphi % because it looks like a p
%
% Miscellaneous shortcuts
% .. over and under
\newcommand{\ss}[1]{_{\substack{#1}}}
\newcommand{\ob}{\overbrace}
\newcommand{\ub}{\underbrace}
\newcommand{\ol}{\overline}
\newcommand{\tld}{\widetilde}
\newcommand{\HAT}{\widehat}
\newcommand{\f}{\frac}
\newcommand{\s}[2]{#1 /\mathopen{}#2}
\newcommand{\rt}{\sqrt}
% .. relations
\newcommand{\sr}{\stackrel}
\newcommand{\sse}{\subseteq}
\newcommand{\ce}{\coloneqq}
\newcommand{\ec}{\eqqcolon}
\newcommand{\ap}{\approx}
\newcommand{\ls}{\lesssim}
\newcommand{\gs}{\greatersim}
% .. miscer
\newcommand{\q}{\quad}
\newcommand{\qq}{\qquad}
\newcommand{\heart}{\heartsuit}
%
% Delimiters
% (I needed to create my own because the MathJax version of \DeclarePairedDelimiter doesn't have \mathopen{} and that messes up the spacing)
% .. one-part
\newcommand{\p}[1]{\mathopen{}\left( #1 \right)}
\newcommand{\b}[1]{\mathopen{}\left[ #1 \right]}
\newcommand{\set}[1]{\mathopen{}\left\{ #1 \right\}}
\newcommand{\abs}[1]{\mathopen{}\left\lvert #1 \right\rvert}
\newcommand{\floor}[1]{\mathopen{}\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\mathopen{}\left\lceil #1 \right\rceil}
\newcommand{\inner}[1]{\mathopen{}\left\langle #1 \right\rangle}
% .... (use phantom to force at least the standard height of double bars)
\newcommand{\norm}[1]{\mathopen{}\left\lVert #1 \vphantom{f} \right\rVert}
\newcommand{\frob}[1]{\norm{#1}_\mathrm{F}}
%% .. two-part
\newcommand{\incond}[2]{#1 \mathop{}\middle|\mathop{} #2}
\newcommand{\cond}[2]{ {\left.\incond{#1}{#2}\right.}}
\newcommand{\pco}[2]{\p{\incond{#1}{#2}}}
\newcommand{\bco}[2]{\b{\incond{#1}{#2}}}
\newcommand{\setco}[2]{\set{\incond{#1}{#2}}}
\newcommand{\at}[2]{\left.#1\right|_{#2}}
% ..... (use phantom to force at least the standard height of double bar)
\newcommand{\oldpara}[2]{#1\vphantom{f} \mathop{}\middle\|\mathop{} #2}
%\newcommand{\para}[2]{#1\vphantom{f} \mathop{}\middle\|\mathop{} #2}
\newcommand{\para}[2]{\mathchoice{\begin{matrix}#1\\\hdashline#2\end{matrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}{\begin{smallmatrix}#1\\\hdashline#2\end{smallmatrix}}}
\newcommand{\ppa}[2]{\p{\para{#1}{#2}}}
\newcommand{\bpa}[2]{\b{\para{#1}{#2}}}
%\newcommand{\bpaco}[4]{\bpa{\incond{#1}{#2}}{\incond{#3}{#4}}}
\newcommand{\bpaco}[4]{\bpa{\cond{#1}{#2}}{\cond{#3}{#4}}}
%
% Levels of closeness
\newcommand{\scirc}[1]{\sr{\circ}{#1}}
\newcommand{\sdot}[1]{\sr{.}{#1}}
\newcommand{\slog}[1]{\sr{\log}{#1}}
\newcommand{\createClosenessLevels}[7]{
\newcommand{#2}{\mathrel{(#1)}}
\newcommand{#3}{\mathrel{#1}}
\newcommand{#4}{\mathrel{#1\!\!#1}}
\newcommand{#5}{\mathrel{#1\!\!#1\!\!#1}}
\newcommand{#6}{\mathrel{(\sdot{#1})}}
\newcommand{#7}{\mathrel{(\slog{#1})}}
}
\let\lt\undefined
\let\gt\undefined
% .. vanilla versions (is it within a constant?)
\newcommand{\ez}{\scirc=}
\newcommand{\eq}{\simeq}
\newcommand{\eqq}{\mathrel{\eq\!\!\eq}}
\newcommand{\eqqq}{\mathrel{\eq\!\!\eq\!\!\eq}}
\newcommand{\lez}{\scirc\le}
\newcommand{\lq}{\preceq}
\newcommand{\lqq}{\mathrel{\lq\!\!\lq}}
\newcommand{\lqqq}{\mathrel{\lq\!\!\lq\!\!\lq}}
\newcommand{\gez}{\scirc\ge}
\newcommand{\gq}{\succeq}
\newcommand{\gqq}{\mathrel{\gq\!\!\gq}}
\newcommand{\gqqq}{\mathrel{\gq\!\!\gq\!\!\gq}}
\newcommand{\lz}{\scirc<}
\newcommand{\lt}{\prec}
\newcommand{\ltt}{\mathrel{\lt\!\!\lt}}
\newcommand{\lttt}{\mathrel{\lt\!\!\lt\!\!\lt}}
\newcommand{\gz}{\scirc>}
\newcommand{\gt}{\succ}
\newcommand{\gtt}{\mathrel{\gt\!\!\gt}}
\newcommand{\gttt}{\mathrel{\gt\!\!\gt\!\!\gt}}
% .. dotted versions (is it equal in the limit?)
\newcommand{\ed}{\sdot=}
\newcommand{\eqd}{\sdot\eq}
\newcommand{\eqqd}{\sdot\eqq}
\newcommand{\eqqqd}{\sdot\eqqq}
\newcommand{\led}{\sdot\le}
\newcommand{\lqd}{\sdot\lq}
\newcommand{\lqqd}{\sdot\lqq}
\newcommand{\lqqqd}{\sdot\lqqq}
\newcommand{\ged}{\sdot\ge}
\newcommand{\gqd}{\sdot\gq}
\newcommand{\gqqd}{\sdot\gqq}
\newcommand{\gqqqd}{\sdot\gqqq}
\newcommand{\ld}{\sdot<}
\newcommand{\ltd}{\sdot\lt}
\newcommand{\lttd}{\sdot\ltt}
\newcommand{\ltttd}{\sdot\lttt}
\newcommand{\gd}{\sdot>}
\newcommand{\gtd}{\sdot\gt}
\newcommand{\gttd}{\sdot\gtt}
\newcommand{\gtttd}{\sdot\gttt}
% .. log versions (is it equal up to log?)
\newcommand{\elog}{\slog=}
\newcommand{\eqlog}{\slog\eq}
\newcommand{\eqqlog}{\slog\eqq}
\newcommand{\eqqqlog}{\slog\eqqq}
\newcommand{\lelog}{\slog\le}
\newcommand{\lqlog}{\slog\lq}
\newcommand{\lqqlog}{\slog\lqq}
\newcommand{\lqqqlog}{\slog\lqqq}
\newcommand{\gelog}{\slog\ge}
\newcommand{\gqlog}{\slog\gq}
\newcommand{\gqqlog}{\slog\gqq}
\newcommand{\gqqqlog}{\slog\gqqq}
\newcommand{\llog}{\slog<}
\newcommand{\ltlog}{\slog\lt}
\newcommand{\lttlog}{\slog\ltt}
\newcommand{\ltttlog}{\slog\lttt}
\newcommand{\glog}{\slog>}
\newcommand{\gtlog}{\slog\gt}
\newcommand{\gttlog}{\slog\gtt}
\newcommand{\gtttlog}{\slog\gttt}
%
% Miscellaneous
\newcommand{\LHS}{\mathrm{LHS}}
\newcommand{\RHS}{\mathrm{RHS}}
% .. operators
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\quasipoly}{quasipoly}
\DeclareMathOperator{\negl}{negl}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
% .. functions
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\err}{err}
\DeclareMathOperator{\ReLU}{ReLU}
% .. analysis
\let\d\undefined
\newcommand{\d}{\operatorname{d}\mathopen{}}
\newcommand{\df}[2]{\f{\d #1}{\d #2}}
\newcommand{\ds}[2]{\s{\d #1}{\d #2}}
\newcommand{\part}{\partial}
\newcommand{\partf}[2]{\f{\part #1}{\part #2}}
\newcommand{\parts}[2]{\s{\part #1}{\part #2}}
\newcommand{\grad}[1]{\mathop{\nabla\!_{#1}}}
% .. sets
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\zo}{\set{0,1}}
\newcommand{\pmo}{\set{\pm 1}}
%
%%% SPECIALIZED MATH %%%
%
% Logic
\renewcommand{\and}{\wedge}
\newcommand{\AND}{\bigwedge}
\newcommand{\or}{\vee}
\newcommand{\OR}{\bigvee}
\newcommand{\xor}{\oplus}
\newcommand{\XOR}{\bigoplus}
\newcommand{\union}{\cup}
\newcommand{\inter}{\cap}
\newcommand{\UNION}{\bigcup}
\newcommand{\INTER}{\bigcap}
\newcommand{\comp}{\overline}
\newcommand{\true}{\r{true}}
\newcommand{\false}{\r{false}}
\newcommand{\tf}{\set{\true,\false}}
\DeclareMathOperator{\One}{\mathbb{1}}
\DeclareMathOperator{\1}{\mathbb{1}}
%
% Linear algebra
\renewcommand{\span}{\mathrm{span}}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\proj}{proj}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\Img}{Im}
\newcommand{\transp}{\mathsf{T}}
\renewcommand{\t}{^\transp}
% ... named tensors
\newcommand{\namedtensorstrut}{\vphantom{fg}} % milder than \mathstrut
\newcommand{\name}[1]{\mathsf{\namedtensorstrut #1}}
\newcommand{\nbin}[2]{\mathbin{\underset{\substack{#1}}{\namedtensorstrut #2}}}
\newcommand{\ndot}[1]{\nbin{#1}{\odot}}
\newcommand{\ncat}[1]{\nbin{#1}{\oplus}}
\newcommand{\nsum}[1]{\sum\limits_{\substack{#1}}}
\newcommand{\nfun}[2]{\mathop{\underset{\substack{#1}}{\namedtensorstrut\mathrm{#2}}}}
\newcommand{\ndef}[2]{\newcommand{#1}{\name{#2}}}
\newcommand{\nt}[1]{^{\transp(#1)}}
%
% Probability
\newcommand{\Normal}{\mathcal{N}}
\let\Pr\undefined
\DeclareMathOperator*{\Pr}{Pr}
\DeclareMathOperator*{\G}{\mathbb{G}}
\DeclareMathOperator*{\Odds}{Od}
\DeclareMathOperator*{\E}{E}
\DeclareMathOperator*{\Var}{Var}
\DeclareMathOperator*{\Cov}{Cov}
\DeclareMathOperator*{\corr}{corr}
\DeclareMathOperator*{\median}{median}
\newcommand{\dTV}{d_{\mathrm{TV}}}
\newcommand{\dHel}{d_{\mathrm{Hel}}}
\newcommand{\dJS}{d_{\mathrm{JS}}}
% ... information theory
\let\H\undefined
\DeclareMathOperator*{\H}{H}
\DeclareMathOperator*{\I}{I}
\DeclareMathOperator*{\D}{D}
%
%%% SPECIALIZED COMPUTER SCIENCE %%%
%
% Complexity classes
% .. classical
\newcommand{\Poly}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\PH}{\mathsf{PH}}
\newcommand{\PSPACE}{\mathsf{PSPACE}}
\renewcommand{\L}{\mathsf{L}}
% .. probabilistic
\newcommand{\formost}{\mathsf{Я}}
\newcommand{\RP}{\mathsf{RP}}
\newcommand{\BPP}{\mathsf{BPP}}
\newcommand{\MA}{\mathsf{MA}}
\newcommand{\AM}{\mathsf{AM}}
\newcommand{\IP}{\mathsf{IP}}
\newcommand{\RL}{\mathsf{RL}}
% .. circuits
\newcommand{\NC}{\mathsf{NC}}
\newcommand{\AC}{\mathsf{AC}}
\newcommand{\ACC}{\mathsf{ACC}}
\newcommand{\TC}{\mathsf{TC}}
\newcommand{\Ppoly}{\mathsf{P}/\poly}
\newcommand{\Lpoly}{\mathsf{L}/\poly}
% .. resources
\newcommand{\TIME}{\mathsf{TIME}}
\newcommand{\SPACE}{\mathsf{SPACE}}
\newcommand{\TISP}{\mathsf{TISP}}
\newcommand{\SIZE}{\mathsf{SIZE}}
% .. keywords
\newcommand{\co}{\mathsf{co}}
\newcommand{\Prom}{\mathsf{Promise}}
%
% Boolean analysis
\newcommand{\harpoon}{\!\upharpoonright\!}
\newcommand{\rr}[2]{#1\harpoon_{#2}}
\newcommand{\Fou}[1]{\widehat{#1}}
\DeclareMathOperator{\Ind}{\mathrm{Ind}}
\DeclareMathOperator{\Inf}{\mathrm{Inf}}
\DeclareMathOperator{\Der}{\mathrm{D}}
\DeclareMathOperator{\Stab}{\mathrm{Stab}}
\DeclareMathOperator{\T}{T}
\DeclareMathOperator{\sens}{\mathrm{s}}
\DeclareMathOperator{\bsens}{\mathrm{bs}}
\DeclareMathOperator{\fbsens}{\mathrm{fbs}}
\DeclareMathOperator{\Cert}{\mathrm{C}}
\DeclareMathOperator{\DT}{\mathrm{DT}}
\DeclareMathOperator{\CDT}{\mathrm{CDT}} % canonical
\DeclareMathOperator{\ECDT}{\mathrm{ECDT}}
\DeclareMathOperator{\CDTv}{\mathrm{CDT_{vars}}}
\DeclareMathOperator{\ECDTv}{\mathrm{ECDT_{vars}}}
\DeclareMathOperator{\CDTt}{\mathrm{CDT_{terms}}}
\DeclareMathOperator{\ECDTt}{\mathrm{ECDT_{terms}}}
\DeclareMathOperator{\CDTw}{\mathrm{CDT_{weighted}}}
\DeclareMathOperator{\ECDTw}{\mathrm{ECDT_{weighted}}}
\DeclareMathOperator{\AvgDT}{\mathrm{AvgDT}}
\DeclareMathOperator{\PDT}{\mathrm{PDT}} % partial decision tree
\DeclareMathOperator{\DTsize}{\mathrm{DT_{size}}}
\DeclareMathOperator{\W}{\mathbf{W}}
% .. functions (small caps sadly doesn't work)
\DeclareMathOperator{\Par}{\mathrm{Par}}
\DeclareMathOperator{\Maj}{\mathrm{Maj}}
\DeclareMathOperator{\HW}{\mathrm{HW}}
\DeclareMathOperator{\Th}{\mathrm{Th}}
\DeclareMathOperator{\Tribes}{\mathrm{Tribes}}
\DeclareMathOperator{\RotTribes}{\mathrm{RotTribes}}
\DeclareMathOperator{\CycleRun}{\mathrm{CycleRun}}
\DeclareMathOperator{\SAT}{\mathrm{SAT}}
\DeclareMathOperator{\UniqueSAT}{\mathrm{UniqueSAT}}
%
% Dynamic optimality
\newcommand{\OPT}{\mathsf{OPT}}
\newcommand{\Alt}{\mathsf{Alt}}
\newcommand{\Funnel}{\mathsf{Funnel}}
%
% Alignment
\DeclareMathOperator{\Amp}{\mathrm{Amp}}
%
%%% TYPESETTING %%%
%
% In text
\renewcommand{\th}{^{\mathrm{th}}}
\newcommand{\degree}{^\circ}
%
% Fonts
% .. bold
\newcommand{\BA}{\boldsymbol{A}}
\newcommand{\BB}{\boldsymbol{B}}
\newcommand{\BC}{\boldsymbol{C}}
\newcommand{\BD}{\boldsymbol{D}}
\newcommand{\BE}{\boldsymbol{E}}
\newcommand{\BF}{\boldsymbol{F}}
\newcommand{\BG}{\boldsymbol{G}}
\newcommand{\BH}{\boldsymbol{H}}
\newcommand{\BI}{\boldsymbol{I}}
\newcommand{\BJ}{\boldsymbol{J}}
\newcommand{\BK}{\boldsymbol{K}}
\newcommand{\BL}{\boldsymbol{L}}
\newcommand{\BM}{\boldsymbol{M}}
\newcommand{\BN}{\boldsymbol{N}}
\newcommand{\BO}{\boldsymbol{O}}
\newcommand{\BP}{\boldsymbol{P}}
\newcommand{\BQ}{\boldsymbol{Q}}
\newcommand{\BR}{\boldsymbol{R}}
\newcommand{\BS}{\boldsymbol{S}}
\newcommand{\BT}{\boldsymbol{T}}
\newcommand{\BU}{\boldsymbol{U}}
\newcommand{\BV}{\boldsymbol{V}}
\newcommand{\BW}{\boldsymbol{W}}
\newcommand{\BX}{\boldsymbol{X}}
\newcommand{\BY}{\boldsymbol{Y}}
\newcommand{\BZ}{\boldsymbol{Z}}
\newcommand{\Ba}{\boldsymbol{a}}
\newcommand{\Bb}{\boldsymbol{b}}
\newcommand{\Bc}{\boldsymbol{c}}
\newcommand{\Bd}{\boldsymbol{d}}
\newcommand{\Be}{\boldsymbol{e}}
\newcommand{\Bf}{\boldsymbol{f}}
\newcommand{\Bg}{\boldsymbol{g}}
\newcommand{\Bh}{\boldsymbol{h}}
\newcommand{\Bi}{\boldsymbol{i}}
\newcommand{\Bj}{\boldsymbol{j}}
\newcommand{\Bk}{\boldsymbol{k}}
\newcommand{\Bp}{\boldsymbol{p}}
\newcommand{\Bq}{\boldsymbol{q}}
\newcommand{\Br}{\boldsymbol{r}}
\newcommand{\Bs}{\boldsymbol{s}}
\newcommand{\Bt}{\boldsymbol{t}}
\newcommand{\Bu}{\boldsymbol{u}}
\newcommand{\Bv}{\boldsymbol{v}}
\newcommand{\Bw}{\boldsymbol{w}}
\newcommand{\Bx}{\boldsymbol{x}}
\newcommand{\By}{\boldsymbol{y}}
\newcommand{\Bz}{\boldsymbol{z}}
\newcommand{\Balpha}{\boldsymbol{\alpha}}
\newcommand{\Bbeta}{\boldsymbol{\beta}}
\newcommand{\Bgamma}{\boldsymbol{\gamma}}
\newcommand{\Bdelta}{\boldsymbol{\delta}}
\newcommand{\Beps}{\boldsymbol{\eps}}
\newcommand{\Bveps}{\boldsymbol{\veps}}
\newcommand{\Bzeta}{\boldsymbol{\zeta}}
\newcommand{\Beta}{\boldsymbol{\eta}}
\newcommand{\Btheta}{\boldsymbol{\theta}}
\newcommand{\Biota}{\boldsymbol{\iota}}
\newcommand{\Bkappa}{\boldsymbol{\kappa}}
\newcommand{\Blambda}{\boldsymbol{\lambda}}
\newcommand{\Bmu}{\boldsymbol{\mu}}
\newcommand{\Bnu}{\boldsymbol{\nu}}
\newcommand{\Bxi}{\boldsymbol{\xi}}
\newcommand{\Bomicron}{\boldsymbol{\omicron}}
\newcommand{\Bpi}{\boldsymbol{\pi}}
\newcommand{\Brho}{\boldsymbol{\rho}}
\newcommand{\Bsigma}{\boldsymbol{\sigma}}
\newcommand{\Btau}{\boldsymbol{\tau}}
\newcommand{\Bupsilon}{\boldsymbol{\upsilon}}
\newcommand{\Bphi}{\boldsymbol{\phi}}
\newcommand{\Bfi}{\boldsymbol{\fi}}
\newcommand{\Bchi}{\boldsymbol{\chi}}
\newcommand{\Bpsi}{\boldsymbol{\psi}}
\newcommand{\Bomega}{\boldsymbol{\omega}}
% .. calligraphic
\newcommand{\CA}{\mathcal{A}}
\newcommand{\CB}{\mathcal{B}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\CD}{\mathcal{D}}
\newcommand{\CE}{\mathcal{E}}
\newcommand{\CF}{\mathcal{F}}
\newcommand{\CG}{\mathcal{G}}
\newcommand{\CH}{\mathcal{H}}
\newcommand{\CI}{\mathcal{I}}
\newcommand{\CJ}{\mathcal{J}}
\newcommand{\CK}{\mathcal{K}}
\newcommand{\CL}{\mathcal{L}}
\newcommand{\CM}{\mathcal{M}}
\newcommand{\CN}{\mathcal{N}}
\newcommand{\CO}{\mathcal{O}}
\newcommand{\CP}{\mathcal{P}}
\newcommand{\CQ}{\mathcal{Q}}
\newcommand{\CR}{\mathcal{R}}
\newcommand{\CS}{\mathcal{S}}
\newcommand{\CT}{\mathcal{T}}
\newcommand{\CU}{\mathcal{U}}
\newcommand{\CV}{\mathcal{V}}
\newcommand{\CW}{\mathcal{W}}
\newcommand{\CX}{\mathcal{X}}
\newcommand{\CY}{\mathcal{Y}}
\newcommand{\CZ}{\mathcal{Z}}
% .. typewriter
\newcommand{\TA}{\mathtt{A}}
\newcommand{\TB}{\mathtt{B}}
\newcommand{\TC}{\mathtt{C}}
\newcommand{\TD}{\mathtt{D}}
\newcommand{\TE}{\mathtt{E}}
\newcommand{\TF}{\mathtt{F}}
\newcommand{\TG}{\mathtt{G}}
\newcommand{\TH}{\mathtt{H}}
\newcommand{\TI}{\mathtt{I}}
\newcommand{\TJ}{\mathtt{J}}
\newcommand{\TK}{\mathtt{K}}
\newcommand{\TL}{\mathtt{L}}
\newcommand{\TM}{\mathtt{M}}
\newcommand{\TN}{\mathtt{N}}
\newcommand{\TO}{\mathtt{O}}
\newcommand{\TP}{\mathtt{P}}
\newcommand{\TQ}{\mathtt{Q}}
\newcommand{\TR}{\mathtt{R}}
\newcommand{\TS}{\mathtt{S}}
\newcommand{\TT}{\mathtt{T}}
\newcommand{\TU}{\mathtt{U}}
\newcommand{\TV}{\mathtt{V}}
\newcommand{\TW}{\mathtt{W}}
\newcommand{\TX}{\mathtt{X}}
\newcommand{\TY}{\mathtt{Y}}
\newcommand{\TZ}{\mathtt{Z}}$
Adapted from lecture 12 of Ryan O’Donnell’s Fall 2017 graduate complexity theory class at CMU, lecture 12c of his Spring 2020 “CS theory toolkit” class (also at CMU), and sections 1.2-1.3 of the lecture notes for Emanuele Viola’s Fall 2017 “Special topics in complexity theory” class at Northeastern.
A distribution $D$ over $\zo^N$ is $k$-wise uniform if looks uniform over every set of $k$ variables. Similarly, a random hash function $h : \zo^n \to \zo$ is $k$-wise uniform if the hashes $h(x_1), \ldots, h(x_k)$ of $k$ distinct inputs are distributed uniformly. In fact (and this took me way too much time to realize), this is the same notion: a $k$-wise uniform hash function over $\zo^n$ corresponds to a $k$-wise uniform distribution over $\zo^{2^n}$: just interpret each of the $2^n$ outputs
\[h(0, \ldots, 0), \ldots, h(1, \ldots, 1)\]
as one coordinate of the distribution. So we will use them interchangeably.
This is equivalent to fooling tests of degree $\leq k$. Indeed,
- if $p$ has degree $\leq k$, then we can decompose $\E_{x \in D}[p(x)]$ into the expectation of its monomials, and those must be fooled since they each depend on only $\leq k$ variables;
- conversely, if $\Pr_{x \in D}[x_S = v] \neq 2^{-k}$ for some set $S$ of $k$ variables and some assignment $v \in \zo^S$, then the polynomial $p(x) \ce \1[x_S = v]$ has degree $k$ and isn’t fooled.
In this note, we’ll try to build $k$-wise uniform distributions and hash functions that can be efficiently computed from a short random seed.
The case $k=1$ is trivial: we just need to make sure that individually, each coordinate of the distribution is $0$ or $1$ with probability $1/2$ each. So we can let $D$ be uniform over the two strings $(0, \ldots, 0)$ and $(1, \ldots, 1)$. In terms of hash functions, we can let $h$ be the all-zeroes or all-ones function with probability $1/2$ each.
This requires only $1$ bit of randomness: the seed length is $1$.
When $k=2$, in addition to making sure $h(x)=1$ with probability $1/2$ for each $x$, we also need to make sure that the outputs $h(x), h(y)$ of two distinct points $x \ne y$ are equal as often as they’re unequal. In particularly, $h(x)$ and $h(y)$ shouldn’t always have the same value.
In the abstract, how would you try to design a hash function $h$ that avoids pairwise collisions? One attempt might be to do some kind of “parity check”, say XOR all the bits together. But for whatever parity check you come up with, there will be some strings $x \neq y$ that nevertheless map to the same value.
On the other hand, taking a random parity check seems more promising: that is, we’ll draw a random “parity check” string $r \in \zo^n$, then hash $x$ to
\[h(x) \ce r\cdot x = r_1x_1 \xor \cdots \xor r_nx_n.\]
If $x \ne y$, then their hashes will differ with probability $1/2$: indeed, the “difference” is $h(x) \xor h(y) = r \cdot (x \xor y)$, and if you take a random parity check of a nonzero string, it will be $1$ with probability $1/2$.
This doesn’t give us pairwise uniformity, though: the issue is that $h(0^n)$ is always $0$. Luckily, this is the only issue, because for every $x$ that’s not the all-zeros string, we do have $h(x)=1$ with probability $1/2$. In fact, this means we already have a pairwise-uniform distribution over $N \ce 2^n-1$ coordinates given by $\set{h(x)}_{x \in \zo^n \setminus \set{0^n}}$.
To get pairwise uniformity, it’s enough to avoid the all-zeros string by first mapping each $x$ to $(x_1, \ldots, x_n, 1) \in \zo^{n+1}$ then taking a random parity check for $r \in \zo^{n+1}$. This is equivalent to drawing a random string $r \in \zo^n$ and a random bit $b \in \zo$, and mapping $x$ to
\[h(x) \ce (r\cdot x) \xor b = r_1x_1 \xor \cdots \xor r_nx_n \xor b.\]
This requires seed length $n+1$ for hash functions, and $\ceil{\log (N + 1)}$ for distributions. And it’s very easy to compute. :)
Dual distance
It’s fairly natural to try and achieve $k$-wise uniformity by making the distribution $D$ uniform over a linear code $C \sse \F_2^N$. Indeed, a linear code $C$ is uniform over a set $S$ of coordinates if and only if it is “complete over $S$”, i.e. $\at{C}{S} = \zo^S$. In particular, this means that $D$ will be $k$-wise uniform as long as any $k$ columns in the generator matrix of $C$ are linearly independent.
For example, the distribution with $N \ce 2^n-1$ coordinates we described in the previous section is the Hadamard code: when $n=3$, it is generated by the matrix $G$ of all nonzero vectors $x \in \zo^3$
\[
G \ce
\begin{pmatrix}
0&0&0&1&1&1&1\\
0&1&1&0&0&1&1\\
1&0&1&0&1&0&1
\end{pmatrix},
%\begin{pmatrix}
%0&0&1\\
%0&1&0\\
%0&1&1\\
%1&0&0\\
%1&0&1\\
%1&1&0\\
%1&1&1
%\end{pmatrix},
\]
with $C \ce \set{r G \mid r \in \zo^3}$. It’s pairwise uniform because any two distinct nonzero vectors $x,y \in \zo^3$ are linearly independent.
The condition “any $k$ columns in $G$ are linearly independent” can be rephrased as “no nonzero vector of Hamming weight $\leq k$ is perpendicular to all rows of $G$”: such a vector would give the coefficients of a linear combination of $\le k$ columns that sums to zero. Since the vectors perpendicular to all rows of $G$ form the dual code $C^\perp$, this is also equivalent to the dual code having distance $>k$ (we call this distance the dual distance).
This means that to find a small $k$-wise uniform distribution $D$, it’s enough to find a large linear code $C^\perp$ with distance $> k$: the parity checks of $C^\perp$ will be the generators of $C$, so their number is the seed length needed. In the example above, $C^\perp$ is the Hamming code, which has distance $>2$ and has the $3$ parity checks indicated by $G$.
General case: Reed-Solomon codes
The Hamming bound tells us that a code of distance $>k$ can only cover a $N^{-\Omega(k)}$ fraction of $\F_2^N$. So in the best case, $C^\perp$ would need $\Omega(k \log N)$ parity checks, and thus the seed length would be at least $\Omega(k \log N)$ in the best case.
Embarrasingly, I don’t know how to match the Hamming bound in general over $\F_2$, but I do know how to do this over larger fields such as $\F_{2^n}$. And fortunately, if we have a $k$-wise uniform distribution over $(\F_{2^n})^m$, we still get a $k$-wise uniform distribution over $\zo^{nm}$ by interpreting the elements of $\F_{2^n}$ as strings in $\zo^n$ and concatenating them together.
Specifically, Reed-Solomon codes are great at achieving dual distance. Pick a field $\F$ of size $\geq m$, and fix $m$ distinct elements $f_1, \ldots, f_m \in \F$ in it (the “evaluation points”). Let $\F[X]^{< k}$ be the set of all polynomials $p(x) = a_0 + a_1x + \cdots + a_{k-1}x^{k-1}$ of degree $< k$. Consider the code $C$ where each codeword is the values of some polynomial $p$ at the evaluation points $f_1, \ldots, f_m$:
\[C \ce \set{(p(f_1), \ldots, p(f_m))\ \middle|\ p \in \F[X]^{<k}}.\]
Polynomials of degree $<k$ are uniquely determined by their value at $k$ distinct points, so $C$ is complete on every set of $k$ points, and therefore the uniform distribution on $C$ is $k$-wise uniform.
Each coefficient $a_i$ takes $\log |\F|$ bits of randomness, so by setting $m \ce N/\log N$ and $\F \ce \F_{2^{\log N}}$, we get a $k$-wise uniform distribution over $\zo^N$ with seed length $O(k \log N)$ as hoped, and it’s very easy to compute.
Note: If you really care, you can get seed length $\floor{k/2}\log N + O(1)$ from BCH codes, and you can generalize that to $\floor{k/2}\log_q N + O(1)$ if both the seeds and the outputs are over $\F_q$ instead of $\zo$.
Lower bounds
We seemed to get the best possible seed length we could have gotten from linear codes, but maybe there was some a more efficient way to do things, with a seed length $s$ much smaller than $k \log N$?
Let’s start with a very basic observation. Consider the matrix $M \in \zo^{2^s \times N}$ whose rows are all possible outcomes of the distribution. If the distribution is pairwise uniform, then at the very least, no two columns shouldn’t be completely identical: otherwise those two coordinates would be perfectly correlated. There are only $2^{2^s}$ possible columns, so we get $N \le 2^{2^s} \Rightarrow s \geq \log \log N$.
But we have a stronger guarantee than this: for any two columns $v,w \in \zo^{2^s}$, we should have that $v_i = w_i$ as often as $v_i \ne w_i$. If we switch the domain from $\zo$ to $\pmo$, this means their inner product $v \cdot w$ is $0$: $v$ and $w$ are orthogonal. A space of dimension $2^s$ cannot have more than $2^s$ pairwise orthogonal vectors, so we have $N \le 2^s \Rightarrow s \ge \log N$.
More generally, if the distribution is $k$-wise uniform, then for any $k$ columns $v^{(1)}, \ldots, v^{(k)}$, the $k$-tuple $(v^{(1)}_i, \ldots, v^{(k)}_i)$ should take every value in $\pmo^k$ equally often. If we split them into two groups (assume $k$ is even), then the products $v^{(1)}_i \cdots v^{(k/2)}_i$ and $v^{(k/2+1)}_i \cdots v^{(k)}_i$ should be equal as often as they’re unequal. This means that the element-wise products $v^{(1)} \circ \cdots \circ v^{(k/2)}$ and $v^{(k/2)+1} \circ \cdots \circ v^{(k)}$ are orthogonal. There are $\binom{N}{k/2}$ such products of $k/2$ columns, so by the same argument we get $\binom{N}{k/2} \leq 2^s \Rightarrow s \geq \floor{k/2} \log (N/k)$.