24 Giving Computational Complexity a Helping Hand

In this chapter we cover a few settings where coding theory turns out to be a useful tool in computational complexity, the field that studies the limits of algorithms and, in particular, the inability of algorithms with limited resources to solve some computational tasks.

24.1 Communication Complexity

24.1.1 (Deterministic) Communication Complexity

\(\)Π\( is given by a tuple \[ (c; P_1,\ldots ,P_c;\pi _1,\ldots ,\pi _c; w) \] where, writing \)X\( for the space of inputs to Alice and \)Y\( for the space of inputs to Bob: \begin{itemize} \item \end{itemize}\)c\( is a non-negative integer denoting the number of bits being communicated. \item \){P_i {X,Y} ∣1 ≤i ≤c}\( determines who speaks in round \)i\(: if \)P_i = X\( then Alice speaks and if \)P_i = Y\(, Bob speaks. \item \)π_i : P_i ×{0,1}^i-1 {0,1}\( describes how the next bit to be communicated depends on the player's input and the past bits of communication. \item \)w : Y ×{0,1}^c O\( is Bob's output at the end of the communication, where \)O\( is the output space. \)

\(\)Π\( as in Definition~ \ref{def:c24-det-protocol} \emph{computes} a function \)f : X ×Y O\( if for every \)(x,y) X×Y\( we have \[ f(x,y) = w(y,b_1,\ldots ,b_c) \] where for every \)i\( we let \)b_i = π_i(z_i,b_1,…,b_i-1)\(, with \)z_i = x\( if \)P_i = X\( and \)z_i = y\( otherwise. \)

\(\)Π= (c,…)\(, denoted \)CC(Π)\(, is defined to be \)c\(. The communication complexity of a function \)f\(, denoted \)CC(f)\(, is the minimum, over all protocols \)Π\( that compute \)f\(, of \)CC(Π)\(. \)

24.1.2 Randomized Communication Complexity

\(\)Π\( is given by a tuple \[ (c;P_1,\ldots ;\pi _1,\ldots ;w;\Omega ) \] where: \begin{itemize} \item \end{itemize}\)c : ΩZ_+\(, such that for each \)r Ω\(, \)c(r)\( denotes the number of bits being communicated with \)r\( being the random bits. \item \){P_i {X,Y} ∣1 ≤i ≤c(r)}\( determines who speaks in round \)i\( for randomness choice \)r Ω\(. \item \)π_i : Ω×P_i ×{0,1}^i-1 {0,1}\( describes how the next bit to be communicated depends on the randomness, the player's input and the past bits of communication. \item \)w : Ω×Y ×{0,1}^c O\( is Bob's output at the end of the communication. \)

\(\)Π\( as in Definition~ \ref{def:c24-rand-protocol} \emph{computes} a function \)f\( if for every \)x X\(, \)y Y\(, we have \[ \Pr _{r \in \Omega }\big[f(x,y) = w(r,y,b_1,\ldots ,b_{c(r)})\big] \ge \frac{2}{3}, \] where \)b_i = π_i(r,z_i,b_1,…,b_i-1)\( and \)z_i\( is as in Definition~ \ref{def:c24-protocol-computes}. \)

\(\)Π= (c;…;Ω)\(, denoted \)CC^R(Π)\(, is defined as \)_rΩ c(r)\(. The randomized communication complexity of a function \)f\(, denoted \)CC^R(f)\(, is the minimum, over all randomized protocols \)Π\( that compute \)f\(, of \)CC^R(Π)\(. \)

24.1.3 Separation between CC(f)\( and \)CC^R(f)

\(\)n ≥1\(, define \)EQ_n : {0,1}^n ×{0,1}^n {0,1}\( by, for any \)x,y {0,1}^n\(, \[ \mathrm{EQ}_n(\mathbf{x},\mathbf{y}) = \begin{cases} 1 & \text{if } \mathbf{x} = \mathbf{y}\\ 0 & \text{otherwise}. \end{cases} \] \)

\(\)n\(, we have \)CC(EQ_n) = n\(. \)

\(\)n\( bits of \)x\( to Bob, who outputs \)1\( if these equal \)y\( and \)0\( otherwise. This uses \)n\( bits of communication and computes \)EQ_n\(, so \)CC(EQ_n) ≤n\(. \emph{Lower bound.} Fix a deterministic protocol \)Π\( that computes \)EQ_n\( with \)c\( bits of communication, and for \)x,y {0,1}^n\( let \)t_x,y = (b_1,…,b_c)\( denote the transcript of the interaction between the players on inputs \)x,y\( (as in Definition~ \ref{def:c24-protocol-computes}). First we claim that if \)t_x,y = t_x’,y’ = t\(, then also \)t_x,y’ = t_x’,y = t\(. Indeed, each bit \)b_i\( of a transcript is determined inductively: if \)P_i = X\( then \)b_i = π_i(z_i, b_1,…,b_i-1)\( depends only on Alice's input \)z_i {x,x’}\( and on the previous bits; if \)P_i = Y\(, only on Bob's input and the previous bits. Since \)t_x,y = t_x’,y’ = t\(, an induction on \)i\( shows that on the input pair \)(x,y’)\( (respectively \)(x’,y)\() every bit sent by Alice, which depends only on \)x\( (resp.\ \)x’\() and the prefix of \)t\(, agrees with the corresponding bit of \)t\(, and likewise for Bob; hence the full transcripts \)t_x,y’\( and \)t_x’,y\( both equal \)t\(. Next, since \)Π\( computes \)EQ_n\( correctly and \)x≠y\( implies \)EQ_n(x,y)=0 ≠1 = EQ_n(x,x)\(, and Bob's output \)w(y,·)\( is a function of \)y\( and the transcript alone, we cannot have \)t_x,x = t_y,y\( for \)x≠y\(: otherwise, applying the previous paragraph with \)(x’,y’) = (y,y)\( would give \)t_x,y = t_y,y\(, so Bob would output \)w(y, t_y,y) = 1\( on input \)(x,y)\(, contradicting correctness since \)EQ_n(x,y) = 0\(. Thus the \)2^n\( transcripts \){t_x,x}_x{0,1}^n\( are pairwise distinct elements of \){0,1}^c\(, forcing \)2^c ≥2^n\(, i.e., \)c ≥n\(. Since \)Π\( was an arbitrary protocol computing \)EQ_n\(, we conclude \)CC(EQ_n) ≥n\(, completing the proof. \)

\(\)Π\( is a \emph{one-way} protocol if in every round Alice is the speaker (i.e., \)P_i = X\( for every \)i\(). We let \)OW-CC(f)\( and \)OW-CC^R(f)\( denote the one-way communication complexities of a function \)f\(. \)

\(\)n ≥c ≥1\( be integers. If there is a \)2^c\(-ary code with \)2^n\( codewords of relative distance \)\( then \[ \mathrm{OW\text{-}CC}^R(\mathrm{EQ}_n) \le c. \] Conversely, if \)OW-CC^R(EQ_n) ≤c\( then there is a \)2^c\(-ary code of relative distance at least \)\(. \)

\(\)E : {0,1}^n Σ^N\( be the encoding function of an error-correcting code with \)2^n\( codewords, \)|Σ| = 2^c\(, and relative distance \)\(, i.e., for every \)x ≠y {0,1}^n\(, \[ \Delta (E(\mathbf{x}),E(\mathbf{y})) \ge \frac{2}{3}\cdot N. \] Design a shared-randomness protocol around \)E\( as follows: (1) Alice and Bob share a random variable \)i\( distributed uniformly over \)[N]\(; (2) on input \)x{0,1}^n\(, Alice sends \)E(x)_i\( to Bob; (3) Bob outputs \)1\( if \)E(x)_i = E(y)_i\( and \)0\( otherwise. This protocol involves \)c\( bits of one-way communication from Alice to Bob. If \)x=y\( then Bob always outputs \)1 = EQ_n(x,y)\(. If \)x≠y\(, then with probability at least \)Δ(E(x),E(y))/N ≥2/3\( over the choice of \)i\( we have \)E(x)_i ≠E(y)_i\(, so Bob outputs \)0 = EQ_n(x,y)\( with probability at least \)2/3\(. Thus the protocol computes \)EQ_n\( correctly with probability \)2/3\( in all cases, showing \)OW-CC^R(EQ_n) ≤c\(. \emph{Reverse direction.} Let \)Π\( be a one-way communication protocol for \)EQ_n\( with \)OW-CC^R(Π) ≤c\(. Let \)m : {0,1}^n ×Ω{0,1}^c\( be the function that determines Alice's message to Bob: on input \)x{0,1}^n\( and randomness \)rΩ\(, \)m(x,r)\( is Alice's message; let \)w(y,r,σ)\( denote Bob's output on input \)y\(, randomness \)r\(, and message \)σ{0,1}^c\( from Alice. Define \)E : {0,1}^n Σ^N\(, with \)Σ={0,1}^c\( and \)N=|Ω|\( (identifying \)Ω\( with \)[N]\(), by \[ E(\mathbf{x})_r = m(\mathbf{x},r), \qquad r \in \Omega . \] Fix \)x≠y\( and consider two scenarios: (i) Alice gets \)x\( and Bob gets \)y\(; (ii) both Alice and Bob get \)y\(. If \)r\( is such that \)E(x)_r = E(y)_r\( then Bob outputs the same value in both scenarios (his output depends only on \)y\(, \)r\(, and Alice's message). In scenario (i) Bob outputs \)1\( with probability at most \)1/3\( (since \)EQ_n(x,y)=0\( and \)Π\( is correct with probability \)≥2/3\(), while in scenario (ii) he outputs \)1\( with probability at least \)2/3\(. Hence the probability that Bob has a different output in the two scenarios is at least \)2/3 - 1/3 = 1/3\(. We conclude that the probability over \)r\( that \)E(x)_r ≠E(y)_r\( is at least \)1/3\(, i.e., \)Δ(E(x),E(y))/N ≥1/3\(. This holds for every \)x≠y\(, so the image of \)E\( is a \)2^c\(-ary code with \)2^n\( codewords of relative distance at least \)1/3\(. \)

24.2 Derandomization and Pseudorandomness

24.2.1 Max t\(-SAT and a randomized algorithm\)

\(\)α[0,1]\(, an algorithm \)A\( that takes as input a \textsc{Max $t$-SAT} instance \)Φ\( and outputs a value \)A(Φ)R\( is said to be an \)\(\)α\(-approximation algorithm\) if for all \(\)Φ\( we have \[ \alpha \cdot \mathrm{opt}(\Phi ) \le A(\Phi ) \le \mathrm{opt}(\Phi ). \] \)

\(\)t\(-SAT formula \)Φ\( on \)n\( variables. \textsc{Output:} A rational number in \)[0,1]\(. \begin{enumerate} \item Pick \end{enumerate}\)a{0,1}^n\( uniformly at random. \item Return \)val(Φ,a)\(. \)

\(\)Φ\( to \textsc{Max $t$-SAT} with \)m\( \)t\(-clauses, we have \[ \mathbb {E}\big[\textsc{Random $t$-SAT}(\Phi )\big] \ge 1 - 2^{-t}. \] \)

\(\)a\( denote the (uniformly random) assignment chosen by \textsc{Random $t$-SAT}\)(Φ)\(, and let \)Z_i\( be the indicator variable that is \)1\( if the \)i\(-th clause \)C_i = ℓ_1∨∨ℓ_t\( is satisfied by \)a\(. The clause \)C_i\( is unsatisfied exactly when \)ℓ_1==ℓ_t=0\(. If two of the literals are complementary (i.e., of the form \)x_j\( and \)x_j\() then \)C_i\( is always satisfied and \)[Z_i=0]=0\(; otherwise the literals involve \)t\( distinct variables and the event \)ℓ_1==ℓ_t=0\( has probability exactly \)2^-t\( (each literal is independently false with probability \)1/2\(). In either case \)E[Z_i] = [Z_i=1] ≥1-2^-t\(. Since \)val(Φ,a) = ∑_i=1^m Z_i\(, linearity of expectation gives \[ \mathbb {E}[\mathrm{val}(\Phi ,\mathbf{a})] = \frac{1}{m}\sum _{i=1}^m \mathbb {E}[Z_i] \ge 1-2^{-t}. \qedhere \] \)

24.2.2 Limited independence

\(\)C\( be a linear \)[n,k,d]_2\( code with encoding function \)E : F_2^k F_2^n\( with the property that its dual \)C^⊥\( is a code of distance at least \)t+1\(. Then \)E\( is a \)t\(-wise independent generator. \item For infinitely many \)n\( and \)t\( there is a linear \)t\(-wise independent generator \)G : {0,1}^s {0,1}^n\( with seed length \)s ≤n\(. \)

\(\)A\( whose output is in the range \)[0,1]\(, input \)x\(, and parameter \)ε[0,1]\(, we say that a generator \)G\( \)\(\)ε\(-weakly fools\) the pair \(\)(A,x)\( if \[ \Big|\mathbb {E}_{\mathbf{y}\in \{ 0,1\} ^m}\big[A(\mathbf{x},\mathbf{y})\big] - \mathbb {E}_{\mathbf{z}\in \{ 0,1\} ^s}\big[A(\mathbf{x},G(\mathbf{z}))\big]\Big| \le \varepsilon . \] \)

\(\)G : {0,1}^s {0,1}^n\( be a \)t\(-wise independent generator. Then \)G\( \)0\(-weakly fools \textsc{Random $t$-SAT}. \)

\(\)t\(-clause \)C\( over the variables indexed by some \)T⊆[n]\( with \)|T|=t\(. Whether \)C\( is satisfied depends only on the values of the variables in \)T\(. Since \)G\( is \)t\(-wise independent, \)G|_T(z)\( is uniformly distributed over \){0,1}^t\( when \)z\( is uniform, so the probability that \)C\( is satisfied by the output of \)G\( equals the probability that \)C\( is satisfied by a uniformly random assignment. Consequently the expected output of \textsc{Random $t$-SAT} on input \)Φ\(, whether its randomness is uniform or the output of \)G\(, equals the (common) average, over \)i\(, of the probability that clause \)C_i\( is satisfied by a uniform assignment (as computed in the proof of Lemma~ \ref{lem:c24-random-t-sat-exp}); these two expectations therefore coincide exactly, i.e., \textsc{Random $t$-SAT} is \)0\(-weakly fooled by \)G\(. \)

\(\)t\(-SAT formula \)Φ\( on \)n\( variables. \textsc{Output:} A rational number in \)[0,1]\(. \begin{enumerate} \item \end{enumerate}\)s ←n\(. \item Pick \)G : {0,1}^s {0,1}^n\( to be a \)t\(-wise independent generator. \item \)v ←0\(. \item For each \)z{0,1}^s\(: \)v ←(v, val(Φ,G(z)))\(. \item Return \)v\(. \)

\(\)1-2^-t\(-approximation algorithm for \textsc{Max $t$-SAT} with running time \)O_t(n^t/2+1)\( time on inputs of length \)n\(. \)

\(\)Φ\( be a formula of length \)n\(, so it has at most \)n\( variables and \)n\( clauses. Algorithm~ \ref{alg:c24-derand-random-t-sat} on input \)Φ\( picks a \)t\(-wise independent generator \)G : {0,1}^s {0,1}^n\( for \)s = (t/2)_2(n+1)\( (guaranteed to exist by Lemma~ \ref{lem:c24-t-wise-indep-code}), runs \textsc{Random $t$-SAT} on every input in the image of \)G\( (i.e., on \)2^s\( random assignments), and outputs the maximum number of clauses satisfied among these. Evaluating \)val(Φ,·)\( at a fixed assignment takes time \)O(n)\(, and there are \)2^s = n^t/2\( assignments to try, so the total running time is \)O(n^1+t/2)\(. By Lemma~ \ref{lem:c24-random-t-sat-fooled}, the expected value of the output of \textsc{Random $t$-SAT} on the random output of \)G\( equals the expected value on true uniform randomness, which by Lemma~ \ref{lem:c24-random-t-sat-exp} is at least \)1-2^-t\( (more precisely at least \)(1-2^-t)·1 ≥(1-2^-t)opt(Φ)\( since \)opt(Φ)≤1\(). Since the algorithm outputs the maximum over the \)2^s\( trials, and the average of these trials is at least \)(1-2^-t)opt(Φ)\(, the maximum \)v\( output is also at least \)(1-2^-t)opt(Φ)\(, so the algorithm is a \)1-2^-t\(-approximation algorithm. \)

24.2.3 ε\(-bias and almost limited independence\)

\(\)A F_2^K×N\( be the generator matrix of an \)ε\(-balanced code. Let \)A_iF_2^K\( denote the \)i\(th column of \)A\(. Then the function \)G : [N] F_2^K\( given by \)G(i) = A_i\( is an \)ε\(-biased generator. \item Let \)G : F_2^s F_2^n\( be an \)ε\(-biased generator. Let \)A F_2^n×2^s\( be the matrix whose \)z\(th column (for \)z{0,1}^s\() is given by \)A_z = G(z)\(. Then \)A\( generates an \)ε\(-balanced code. \)

\(\)ℓ: F_2^K F_2\( be a non-zero linear function; write \)ℓ(x) = v·x\( for some non-zero \)vF_2^K\(. Then \)c := vA\( is a codeword of the code generated by \)A\( (as \)v≠0\( and \)A\( has \)K\( independent rows, \)c\( is a non-zero codeword), and its \)i\(-th coordinate is \)v·A_i = ℓ(G(i))\(. Since the all-zero vector \)0\( is also a codeword and \)c≠0\(, the \)ε\(-balanced property applied to the pair \)(0,c)\( gives \[ \left(\tfrac 12-\varepsilon \right)N \le \Delta (\mathbf{0},\mathbf{c}) = \mathrm{wt}(\mathbf{c}) = \# \{ i : \ell (G(i))=1\} \le \left(\tfrac 12+\varepsilon \right)N. \] Dividing by \)N\( and noting that \)i\( is uniform on \)[N]\( gives \)|_i[ℓ(G(i))=1] - 1/2| ≤ε\(, as required. \emph{Part 2.} Let \)C\( be the code with generator matrix \)A\(, i.e., \)C = {xA : xF_2^n}⊆F_2^2^s\(. Let \)c = xA ≠c’ = yA\( be two distinct codewords, and set \)v = x+y ≠0\( (using \)x≠y\(, else \)c=c’\(). Then \)c-c’ = vA\(, and its coordinate at \)z{0,1}^s\( equals \)v·A_z = ℓ_v(G(z))\( where \)ℓ_v\( is the (non-zero) linear function \)ℓ_v(w) = v·w\(. Hence \[ \Delta (\mathbf{c},\mathbf{c}') = \mathrm{wt}(\mathbf{c}-\mathbf{c}') = \# \{ \mathbf{z}\in \{ 0,1\} ^s : \ell _{\mathbf{v}}(G(\mathbf{z}))=1\} = 2^s\cdot \Pr _{\mathbf{z}}\big[\ell _{\mathbf{v}}(G(\mathbf{z}))=1\big]. \] Since \)G\( is \)ε\(-biased, this probability lies in \)[1/2-ε,1/2+ε]\(, so, writing \)N=2^s\(, \)Δ(c,c’) [(1/2-ε)N,(1/2+ε)N]\(, as required. \)

\(\)ε>0\( and every sufficiently large \)n\(, there exists an \)ε\(-biased generator \)G : F_2^s F_2^n\(, where \)s = (n/ε^2) + O(1)\(. Furthermore, if we allow \)s = (n^2/ε^2)+O(1)\(, or \)s = (n/ε^3)+O(1)\(, then this generator runs in time \)poly(n/ε)\(. \)

\(\)D_1,D_2\( with the same support set \)S\( is \[ \frac{1}{2}\sum _{x\in S}\Big|\Pr _{X\sim \mathscr {D}_1}[X=x] - \Pr _{Y\sim \mathscr {D}_2}[Y=x]\Big|. \] \)

\(\)ε≥0\(, if \)G : F_2^s F_2^n\( is an \)ε\(-biased generator, then the output of \)G\( is \)2^n·ε\( close to uniform in total variation distance. \)

\(\)xF_2^n\(, \)|_z[G(z)=x] - 2^-n| ≤2ε\(; the lemma follows since the total variation distance of \)G(z)\( from uniform equals \)∑_x|_z[G(z)=x]-2^-n| ≤2^n-1·2ε= 2^nε\(. Fix \)xF_2^n\(. Let \)1_x(y)\( be \)1\( if \)y=x\( and \)0\( otherwise. For \)αF_2^n\( let \)L_α(y) = ∑_i=1^n α_i y_i\( and let \)χ_α(y) = (-1)^L_α(y)\( (a real-valued function). By the \)ε\(-bias of \)G\( we have \)|E_z[χ_α(G(z))]| ≤2ε\( for every \)αF_2^n∖{0}\( (this quantity equals \)|2_z[L_α(G(z))=0]-1| = |1-2_z[L_α(G(z))=1]| ≤2ε\(). We may write \[ \mathbb {1}_{\mathbf x}(\mathbf y) = \frac{1}{2^n} \left(\sum _{\alpha :\chi _\alpha (\mathbf x)=1} \chi _\alpha (\mathbf y) - \sum _{\alpha :\chi _\alpha (\mathbf x)=-1}\chi _\alpha (\mathbf y)\right). \] Since \)E_z[χ_0(G(z))]=1\( (as \)χ_0\( is constantly \)1\(), we get \begin{align*} \big|\mathbb {E}_{\mathbf z}\big[\mathbb {1}_{\mathbf x}(G(\mathbf z))\big] - 2^{-n}\big| & = \left|\mathbb {E}_{\mathbf z}\left[\frac{1}{2^n}\left(\sum _{\alpha \in \mathbb {F}_2^n\setminus \{ 0\} :\chi _\alpha (\mathbf x)=1}\chi _\alpha (G(\mathbf z)) - \sum _{\alpha :\chi _\alpha (\mathbf x)=-1}\chi _\alpha (G(\mathbf z))\right)\right]\right|\\ & \le \frac{1}{2^n}\sum _{\alpha \in \mathbb {F}_2^n\setminus \{ 0\} } \big|\mathbb {E}_{\mathbf z}[\chi _\alpha (G(\mathbf z))]\big|\\ & \le \frac{2^n-1}{2^n}(2\varepsilon ) \le 2\varepsilon , \end{align*} as desired. \)

\(\)t\( and \)ε≥0\(, if \)G : F_2^s F_2^n\( is an \)ε\(-biased generator, then \)G\( is also a \)δ\(-almost \)t\(-wise independent generator, for \)δ= ε·2^t\(. \)

\(\)T⊆[n]\( be a set of cardinality \)t\(, and let \)G|_T : F_2^s F_2^t\( be the projection of the output of \)G\( to the coordinates of \)T\(, writing \)G|_T(z) = (x_i_1,…,x_i_t)\( where \)G(z)=(x_1,…,x_n)\( and \)T={i_1,…,i_t}\(. It follows directly from the definition of \)ε\(-bias that \)G|_T\( is also \)ε\(-biased: every non-zero linear function on \)F_2^t\(, precomposed with the coordinate projection to \)T\(, is a non-zero linear function on \)F_2^n\( supported on \)T\(, and \)G\( \)ε\(-fools it by assumption. Applying Lemma~ \ref{lem:c24-eps-biased-close-uniform} to \)G|_T\( (viewed as a generator \)F_2^sF_2^t\(), we get that the output of \)G|_T\( is \)ε·2^t\( close in total variation distance to the uniform distribution on \){0,1}^t\(. Since this holds for every \)T⊆[n]\( of cardinality \)t\(, \)G\( is \)ε2^t\(-almost \)t\(-wise independent. \)

\(\)G : {0,1}^s {0,1}^n\( be a \)δ\(-almost \)t\(-wise independent generator. Then \)G\( \)(2δ)\(-weakly fools \textsc{Random $t$-SAT}. \)

\(\)Φ= (C_1,…,C_m)\( be a \)t\(-SAT formula, and for each \)i\( let \)T_i⊆[n]\(, \)|T_i|=t\(, be the set of variables appearing in \)C_i\(, and let \)Z_i : {0,1}^n {0,1}\( be the indicator of \)C_i\( being satisfied; note \)Z_i\( depends only on the coordinates in \)T_i\(, and \)0≤Z_i≤1\(. For any two distributions \)D_1,D_2\( on a common finite support with total variation distance \)δ\(, and any \)[0,1]\(-valued function \)f\( on that support, we have \)|E_D_1[f] - E_D_2[f]| ≤2δ\( (this is immediate from the definition of total variation distance, writing \)f\( as a difference of indicators of level sets and using the triangle inequality, or directly from \)|E_D_1[f]-E_D_2[f]| ≤∑_x |_D_1[x]-_D_2[x]|·f(x) ≤∑_x|_D_1[x]-_D_2[x]| = 2δ\(). Since \)G\( is \)δ\(-almost \)t\(-wise independent, \)G|_T_i(z)\( (for \)z\( uniform) is \)δ\(-close in total variation to uniform on \){0,1}^t\(. Applying the fact above to \)f = Z_i\( (viewed as a function of the coordinates in \)T_i\() gives \[ \big|\mathbb {E}_{\mathbf z}[Z_i(G(\mathbf z))] - \mathbb {E}_{\mathbf y}[Z_i(\mathbf y)]\big| \le 2\delta \] for each \)i=1,…,m\(. Since \)val(Φ,·) = ∑_i=1^m Z_i\(, averaging over \)i\( gives \[ \big|\mathbb {E}_{\mathbf z}[\mathrm{val}(\Phi ,G(\mathbf z))] - \mathbb {E}_{\mathbf y}[\mathrm{val}(\Phi ,\mathbf y)]\big| \le \frac{1}{m}\sum _{i=1}^m \big|\mathbb {E}_{\mathbf z}[Z_i(G(\mathbf z))] - \mathbb {E}_{\mathbf y}[Z_i(\mathbf y)]\big| \le 2\delta , \] i.e., \)G\( \)(2δ)\(-weakly fools \textsc{Random $t$-SAT}. \)

\(\)1-2^-t\(-approximation algorithm for \textsc{Max $t$-SAT} with running time \)O(4^t·n^5)\( time on inputs of length \)n\(. \)

\(\)φ\( be a \)t\(-CNF formula of length \)n\(; in particular \)φ\( has at most \)n\( variables and \)m ≤n\( clauses. Set \[ \delta = \frac{1}{2^{t+2}m}, \qquad \varepsilon = 2^{-t}\delta . \] Let \)G : F_2^s F_2^n\( be an \)ε\(-biased generator as in Lemma~ \ref{lem:c24-eps-biased-exists}; by Lemma~ \ref{lem:c24-eps-biased-almost-t-wise}, \)G\( is \)δ\(-almost \)t\(-wise independent. By Lemma~ \ref{lem:c24-almost-t-wise-fools}, \)G\( \)2δ\(-weakly fools \textsc{Random $t$-SAT}, i.e., \[ \mathbb {E}_{\mathbf z}[\mathrm{val}(\Phi ,G(\mathbf z))] \ge (1-2^{-t}) - 2\delta , \] using Lemma~ \ref{lem:c24-random-t-sat-exp} for the uniform expectation. In particular, there exists \)z\( such that \[ \mathrm{val}(\Phi ,G(\mathbf z)) \ge 1-2^{-t}-2\delta = 1-2^{-t}-2^{-(t+1)}/m. \] But \)val(φ,x)\( is always an integral multiple of \)1/m\(, and so if \[ \mathrm{val}(\Phi ,G(\mathbf z)) \ge 1-2^{-t}-2^{-t+1}/m, \] then \)val(Φ,G(z)) ≥1-2^-t\(. Thus we only need to search over a space of size \)2^s\( to find such a \)z\(, and by Lemma~ \ref{lem:c24-eps-biased-exists} we can take \)s = (n^2/ε^2) + O(1)\( so that \)2^s = O(n^2/ε^2) = O(4^t n^4)\( (using \)ε= 2^-tδ= Θ(2^-2t/m)\( and \)m ≤n\(). Computing \)val(φ,x)\( for any given \)x\( takes \)O(n)\( time, leading to the claimed running time \)O(4^t n^5)\(. \)

\(\)G_1 : F_2^s F_2^ℓ\( be an \)ε\(-biased generator. Let \)G_2 : F_2^ℓF_2^n\( be a linear \)t\(-wise independent generator. Then \)G : F_2^s F_2^n\( given by \)G(z) = G_2(G_1(z))\( is an \)(ε·2^t)\(-almost \)t\(-wise independent generator. \)

\(\)T⊆[n]\( with \)|T|=t\( and let \)G|_T\( and \)G_2|_T\( denote the projections of \)G\( and \)G_2\( (resp.) to the coordinates in \)T\(, so \)G|_T(z) = G_2|_T(G_1(z))\(. \)Claim: \(\)G|_T\( is \)ε\(-biased.\) Let \(\)L : F_2^t F_2\( be a non-zero linear function. Since \)G_2 : F_2^ℓF_2^n\( is linear, \)G_2|_T\( is also linear, and so \)L’ := L ○G_2|_T : F_2^ℓF_2\( is linear. We show \)L’\( is not the zero function: since \)L\( is non-zero, there is \)aF_2^t\( with \)L(a)≠0\(. Since \)G_2\( is \)t\(-wise independent, \)G_2|_T(y)\( is uniformly distributed for uniformly random \)yF_2^ℓ\(, so in particular there is \)bF_2^ℓ\( with \)G_2|_T(b)=a\(. Then \)L’(b) = L(G_2|_T(b)) = L(a) ≠0\(, so \)L’\( is non-zero. By the \)ε\(-bias of \)G_1\(, \[ \Big|\Pr _{\mathbf z\in \mathbb {F}_2^s}\big[L(G|_T(\mathbf z))=1\big] - \tfrac 12\Big| = \Big|\Pr _{\mathbf z\in \mathbb {F}_2^s}\big[L'(G_1(\mathbf z))=1\big] - \tfrac 12\Big| \le \varepsilon . \] Since \)L\( was an arbitrary non-zero linear function on \)F_2^t\(, \)G|_T\( is \)ε\(-biased. Now, by Lemma~ \ref{lem:c24-eps-biased-close-uniform} applied to \)G|_T\( (as a generator \)F_2^s F_2^t\(), its output is \)ε·2^t\( close to uniform in total variation distance. Since this holds for every \)T⊆[n]\( with \)|T|=t\(, \)G\( is an \)(ε·2^t)\(-almost \)t\(-wise independent generator. \)

\(\)δ>0\(, integer \)t\(, and every sufficiently large \)n\(, there exists a polynomial time computable \)δ\(-almost \)t\(-wise independent generator \)G : F_2^s F_2^n\(, where \[ s = 2\big(t + \log 1/\delta + \log \log n\big) + O(1). \] \)

\(\)ℓ= ·n\( and let \)G_2 : F_2^ℓF_2^n\( be the map given by Lemma~ \ref{lem:c24-t-wise-indep-code} (part 2), so \)G_2\( is \)t\(-wise independent and linear. Set \[ \varepsilon = 2^{-t}\delta , \] so that (per Lemma~ \ref{lem:c24-eps-biased-exists}) \[ s = \log (\ell ^2/\varepsilon ^2) + O(1) = 2t + \log (\ell ^2/\delta ^2)+O(1) = 2t + \log (1/\delta ^2) + 2\log \log n + O(1), \] matches the claimed seed length up to constants. Let \)G_1 : F_2^s F_2^ℓ\( be an \)ε\(-biased map as given by Lemma~ \ref{lem:c24-eps-biased-exists} (running in time \)poly(ℓ/ε)\(, hence polynomial in \)n,1/δ\(). Letting \)G = G_2 ○G_1\( and applying Lemma~ \ref{lem:c24-compose-almost-t-wise} (with parameter \)ε·2^t = δ\() yields that \)G\( is a \)δ\(-almost \)t\(-wise independent generator with the claimed seed length and running time polynomial in \)n\( and \)1/δ\(. \)

\(\)δ>0\(, there is a deterministic \)1-2^-t-δ\(-approximation algorithm for \textsc{Max $t$-SAT} with running time \)O(4^t/δ^2 ·n(n)^2)\( time on inputs of length \)n\(. \)

\(\)φ\( be a \)t\(-CNF formula of length \)n\(, with at most \)n\( variables and \)m≤n\( clauses. Apply Lemma~ \ref{lem:c24-poly-time-almost-t-wise} with parameter \)δ/2\( in place of \)δ\( to obtain a polynomial time computable \)(δ/2)\(-almost \)t\(-wise independent generator \)G : F_2^s F_2^n\( with seed length \[ s = 2\big(t+\log (2/\delta )+\log \log n\big)+O(1) = 2\big(t+\log (1/\delta )+\log \log n\big)+O(1). \] By Lemma~ \ref{lem:c24-almost-t-wise-fools}, \)G\( \)δ\(-weakly fools \textsc{Random $t$-SAT}, so using Lemma~ \ref{lem:c24-random-t-sat-exp}, \[ \mathbb {E}_{\mathbf z}[\mathrm{val}(\Phi ,G(\mathbf z))] \ge (1-2^{-t}) - \delta . \] Hence there exists \)z{0,1}^s\( with \)val(Φ,G(z)) ≥1-2^-t-δ\(. Searching over all \)2^s\( choices of \)z\( and evaluating \)val(φ,·)\( (in time \)O(n)\( per evaluation) finds such a \)z\(, giving a deterministic \)(1-2^-t-δ)\(-approximation algorithm. The running time is \)O(n)·2^s = On·4^t ·(1/δ)^2·(n)^2\(, as claimed (using \)2^2n = (n)^2\(). \)

24.3 Hardcore Predicates

\(\)f : {0,1}^* {0,1}^*\( (where \){0,1}^* = ∪_nZ_≥0{0,1}^n\() is a \emph{permutation} if: \begin{enumerate} \item \end{enumerate}\)f\( is length-preserving, i.e., for every \)n\( and \)x{0,1}^n\( we have \)f(x){0,1}^n\(; and \item \)f\( is invertible, i.e., there is \)f^-1 : {0,1}^*{0,1}^*\( such that for every \)x{0,1}^*\(, \)f^-1(f(x)) = x\(. \)

\(\)f : {0,1}^*{0,1}^*\( is \emph{easy} if there is a polynomial time algorithm \)A\( that computes \)f\(, i.e., for every \)x{0,1}^*\(, \)A(x) = f(x)\(. \item A function \)f\( is said to be \emph{(merely) hard} if it is not easy. \item For a function \)α: Z_≥0[0,1]\(, we say that \)f\( is \)\(\)α\(-hard\) if for every polynomial time algorithm \(\)A\( and for every sufficiently large \)nZ_≥0\( we have \[ \Pr _{\mathbf x\in \{ 0,1\} ^n}\big[A(\mathbf x)=f(\mathbf x)\big] \le \alpha (n). \] \item We say that \)f\( is \emph{very hard} if for every constant \)c≥0\( we have that \)f\( is \)\(-hard. \)

\(\)f : {0,1}^*{0,1}^*\( is said to be a \emph{one-way permutation} if (1) \)f\( is easy and (2) \)f^-1\( is very hard. \)

\(\)ε>0\(, we say that a Boolean function (predicate) \)b : {0,1}^k{0,1}\( is an \)\(\)ε\(-hardcore predicate\) for a permutation \(\)f : {0,1}^k {0,1}^k\( if: \begin{enumerate} \item \end{enumerate}\)b\( is easy, and \item \)b○f^-1\( is \)+ε\(-hard. \)

We say that \(\)b\( is a \emph{hardcore predicate} for \)f\( if \)b\( is \)k^-c\(-hardcore for \)f\( for every \)c≥0\(. \)

\(\)E : {0,1}^k {0,1}^n\( is \)\(\)(ρ,L)\(-efficiently-list-decodable\) if there is an efficient algorithm \(\)L\( (a list-decoding algorithm) such that: \begin{enumerate} \item For every \end{enumerate}\)y{0,1}^n\(, \)D(y)⊆{0,1}^k\( satisfies \)|D(y)|≤L\(; and \item For every \)x{0,1}^k\( such that \)Δ(E(x),y)≤ρn\(, we have \)xD(y)\(. \)

\(\)f : {0,1}^k {0,1}^k\( be a one-way permutation and let \)E : {0,1}^k {0,1}^n\( be a \)(1/2-ε,L)\(-efficiently list decodable code with \)n=2^t\( for some integer \)t\(. Let \)F : {0,1}^k+t{0,1}^k+t\( be the padding of \)f\( given by \)F(x,i) = (f(x),i)\( for \)i{0,1}^t\(. Finally let \)b : {0,1}^k+t{0,1}\( be given by \)b(x,i) = E(x)_i\( where \)i{0,1}^t\( is viewed as an element of \)[n]\( and \)E(x)_i\( denotes the \)i\(th coordinate of \)E(x)\(. Then \)b\( is \)(2ε)\(-hardcore for \)F\(. \)

\(\)b\( is not \)2ε\(-hardcore for \)F\(, and let \)A : {0,1}^k+t{0,1}\( be a polynomial time algorithm showing this. This means \[ \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i) = E(\mathbf x)_i\big] \ge \frac12+2\varepsilon . \] We show how to use \)A\( to invert \)f\( with high probability, via Algorithm~ \ref{alg:c24-invert-f}. Its running time is clearly bounded by a polynomial in \)n\( (since \)A\(, \)f\(, and the list-decoding algorithm \)D\( are all efficient). We now analyze the probability that Algorithm~ \ref{alg:c24-invert-f} successfully outputs \)x\( given \)w = f(x)\( as input. Let \[ G = \left\{ \mathbf x \; \middle |\; \Pr _i\big[A(f(\mathbf x),i)=E(\mathbf x)_i\big] \ge \frac12+\varepsilon \right\} . \] We note that \[ \frac12+2\varepsilon \le \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i)=E(\mathbf x)_i\big] \le \Pr _{\mathbf x}[\mathbf x\in G] + \frac12+\varepsilon , \] where the upper bound follows since \begin{align*} \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i)=E(\mathbf x)_i\big] & = \Pr _{\mathbf x}[\mathbf x\in G]\cdot \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i)=E(\mathbf x)_i \mid \mathbf x\in G\big]\\ & \qquad + \Pr _{\mathbf x}[\mathbf x\notin G]\cdot \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i)=E(\mathbf x)_i \mid \mathbf x\notin G\big]\\ & \le \Pr _{\mathbf x}[\mathbf x\in G] + \Pr _{\mathbf x,i}\big[A(f(\mathbf x),i)=E(\mathbf x)_i\mid \mathbf x\notin G\big], \end{align*} and by definition of \)G\(, the second term is \)≤+ε\( when \)x G\( (since \)xG\( means the probability over \)i\( is \)< + ε\(). This proves the upper bound above, and rearranging gives \[ \Pr _{\mathbf x}[\mathbf x\in G] \ge \varepsilon . \] We now argue that if \)xG\( then Algorithm~ \ref{alg:c24-invert-f} outputs \)x\(. To see this, note that by definition of \)G\(, letting \)y=(A(f(x),i))_i\(, we have \[ \Delta (E(\mathbf x),\mathbf y) \le \left(\frac12-\varepsilon \right)n. \] By the property of the list-decoder for \)E\(, this implies \)xS D(y)\(, and since \)f(x)=w\(, the algorithm reports \)x\( as output. Thus Algorithm~ \ref{alg:c24-invert-f} inverts \)f\( correctly on a \)≥ε\( fraction of inputs \)x\(, in polynomial time, contradicting that \)f^-1\( is very hard (since \)f\( is a one-way permutation). This contradiction shows \)b\( is \)2ε\(-hardcore for \)F\(, as desired. \)

24.4 Average case complexity

\(\)F\( and matrix \)MF^n×n\( with \)M = [m_i,j]_i,j[n]\(, the \emph{Permanent} of \)M\(, denoted \)perm(M)\(, is the quantity \[ \mathrm{perm}(M) = \sum _{\pi \in S_n}\prod _{i=1}^n m_{i,\pi (i)} \] where \)S_n = {π: [n][n] : π invertible}\( is the set of permutations over \)[n]\(. \)

\(\)NP\(-hard. Specifically there are polynomial time algorithms \)A\( and \)B\( such that for every instance \)φ\( of satisfiability, we have \)A(φ) = (F_q,n,M)\( where \)MF_q^n×n\( and \)B(perm(M))=1\( if and only if \)φ\( is satisfiable. \)

\(\)f\( and family of distributions \)D = {D_n}_n\( where \)D_n\( is a distribution on inputs of length \)n\(, we say that the pair \)(f,D)\( is in \emph{average polynomial time} if there exists a polynomial time algorithm \)A\( such that for every \)n\(, we have \[ \Pr _{\mathbf x \sim D_n}\big[f(\mathbf x)\ne A(\mathbf x)\big] \le \frac{1}{10}. \] \)

\(\)D = {D_n}_n\( be a family of distributions given as follows: given \)n\(, let \)p=p(n)[30n,60n]\( be a fixed prime, and let \)D_n\( be a uniformly random matrix \)MF_p^n×n\(. Then if the pair \)(perm,D)\( is in average polynomial time, then \)perm(M)\( is computable in randomized polynomial time for every matrix in the support of \)D\(. \)

\(\)(perm,D)\( being in average polynomial time, let \)A\( be a polynomial time algorithm such that \[ \Pr _{M\in \mathbb {F}_p^{n\times n}}\big[A(M)\ne \mathrm{perm}(M)\big] \le \frac{1}{10}. \] Define the polynomial over the "matrix" of variables \)X = {X_i,j}_i,j[n]\(: \[ P(\mathbf X) = \sum _{\pi \in S_n}\prod _{i=1}^n X_{i,\pi (i)}, \] a multivariate polynomial of degree \)n\( in \)n^2\( variables, so that for any \)MF_p^n×n\( we have \)perm(M) = P(M)\(. Thus the vector \)c = (P(M))_MF_p^n×n\( is a valid codeword in the Reed-Muller code \)RM(p,n^2,n)\(. Define also \)y = (A(M))_MF_p^n×n\(. By our bound on \)A\(, \)δ(c,y) ≤\(. It can be verified that this fraction of errors is less than half the distance of \)RM(p,n^2,n)\(; however decoding \)y\( in its entirety via a global decoder would incur runtime polynomial in the block length \)p^n^2\(, which is too expensive. Instead we do not need to decode \)y\( in its entirety: given any \)MF_p^n×n\(, we are only interested in computing \)c_M = perm(M)\(, using a \emph{local} decoder / corrector for the Reed-Muller code with oracle access to \)y\( (simulated, since \)A\( is a polynomial time algorithm, by computing \)A(M’)\( for any needed \)M’F_p^n×n\( in polynomial time). Such a local corrector makes at most \)p-1\( oracle calls and has overall runtime \)poly(p,n^2) = poly(n)\( (since \)p=O(n)\(), and its correctness requires \[ \delta (\mathbf c,\mathbf y) \le \frac16\left(1-\frac{n+1}{p-1}\right). \] Combined with \)δ(c,y)≤\(, it suffices to ensure \[ \frac16\left(1-\frac{n+1}{p-1}\right) {\gt} \frac{1}{10}, \] which holds provided \) < \(, i.e., provided \)p > 15(n+1)+1\(. This is satisfied by our choice of \)p[30n,60n]\( (the existence of a prime in this range follows from known results on the distribution of primes). Running the local corrector at any input matrix \)M\( in the support of \)D\( (using oracle access to \)A\(, simulated in polynomial time as above) then computes \)perm(M)\( correctly with probability at least \)2/3\(, in overall polynomial time, completing the proof. \)

\(\)N=2^n\( and \)K=2^k\(, and let \)C : {0,1}^K {0,1}^N\( be a \)polylog N,\(-locally decodable code. Given a function \)f : {0,1}^k {0,1}\(, let \)F : {0,1}^n {0,1}\( be the function \)F = f○C\(. If \)F\( is in average polynomial time, then \)f\( is computable in randomized polynomial time (on worst-case instances). \)

\(\)A\( be a polynomial time algorithm showing that \)F\( is in average polynomial time, so \[ \Pr _{x\in \{ 0,1\} ^n}\big[A(x)\ne F(x)\big] \le \frac{1}{10}. \] Let \)T(A){0,1}^N\( denote the vector \)T(A)_x = A(x)\(. Changing notation, and using \)F=f○C\(, we have \[ \delta \big(T(A), C(T(f))\big) \le \frac{1}{10}, \] where \)T(f){0,1}^K\( similarly denotes the truth table of \)f\( (i.e., \)C(T(f))\( is the codeword encoding the full truth table of \)f\(). Let \)D\( be the local decoding algorithm for \)C\( (given by the \)(polylog N,1/10)\(-local decodability hypothesis). Then for every \)y{0,1}^k\(, with probability at least \)2/3\( (over the coin tosses of \)D\(), \)D^T(A)(y) = f(y)\(. The call \)D^T(A)\( can be simulated in \)polylog K\( time, since \)D\( runs in \)polylog N = polylog K\( time given oracle access to \)T(A)\(, and oracle access to \)T(A)\( amounts simply to computing \)A\(, which takes time polynomial in \)n\(. Since \)N = O(K) = O(k)\(, this shows that \)f\( can be computed on every input \)y {0,1}^k\( in time polynomial in \)k\( by a probabilistic algorithm that is correct with probability at least \)2/3\( on every input, i.e., \)f\( is computable in randomized polynomial time on worst-case instances. \)