Worst-Case to Average-Case Reductions via Additive Combinatorics

by Vahid Asadi, Sasha Golovnev, Tom Gur, Igor Shinkar and Sathyawageeswar Subramanian

Oded's comments

The randomized reduction is based on the observation that the correctness of the result can be verified in linear (in the input size) time. Hence, it suffices to produce the correct result with non-negligible probability. The following overview refers to an algorith, denoted $P$, that, given two random $n$-by-$n$ matrices over $\F=GF(2)$, produces their produce with probability at least $\beta$. Hence, for at least $\alpha=\beta/2$ fraction of the mattrices $A$, it holds that $\prob_{B}[P(A,B)=AB]\geq\alpha$.

Fixing such a matrix $A$, we denote the set of matrices $B$ such that $P(A,B)=AB$ by $\X$ and note that the span of $\X$ has co-dimension at most $\log_2(1/\alpha)$. A result from additive combinatorics asserts that $\X+\X+\X+\X$ is contained in a subspace of co-dimension at most $O(1/\alpha^2)$. Furthermore, $\X+\X+\X+\X$ is contined in a subspace $\Y$ of co-dimension $O(1/\alpha^2)$ such that for every $V\in \Y$ it holds that $$\prob_{R,S,T\in \X}[V-(R+S+T)\in \X]=\Omega(\alpha^2)$.

Letting $k=O(1/\alpha^2)$, the next observation is that, for every matrix $B$, if we select a random $n$-by-$n$ matrix $M$ of rank $k$, then $\prob_M[B+M \in \Y] \geq 2^{-k}$. Actually, let use select $M$ by selecting a random $n$-by-$k$ matrix $K$ and a random $k$-by-$n$ matrix $L$, and use $M=KL$. Then, $\prob_{K,L}[B+KL \in \Y] = \prob_{K,L}[KL \in \Y-B]$, equals the probability that $KL$ satisfies the $k$ affine constraints of the affine subspace $\Y-B$, which is at least $4^{-k}$. The reduction just tries the following two cases, while verifying the answer in each case.

  1. If $B\in \Y$, then a random selection of matrices $R,S,T$ satisfies $R,S,T,(B-R-S-T)\in \Y$ with probability at least $\Omega(\alpha^5)$, whereas when the event occurs $AB = P(A,R)+P(A,S)+P(A,T)+P(A,B-R-S-T)$ holds.
  2. Otherwise, $\prob_{K,L}[B+KL \in \Y] \geq 4^{-k}$, whereas when the event occurs $AB = A(B+KL)-AKL$ holds, where $A(B+KL)$ is computed as in the first case. The point is that $AKL$ can be computed in $O(n^2k)$ time, since $C=AK$ is an $n$-by-$k$ matrix whose entries are inner-products of $n$-long vectors and $CL$ is an $n$-by-$n$ matrix whose entries are products of $k$-long vectors.
Hence, using $P$, which is correct on an $\beta$ fraction of the matrix pairs, we obtained a randominzed $P'$ such that for at least a $\beta/2$ fraction of the first operand (i.e., $A$'s) it holds that $P'$ is correct on all choices of the second operand (i.e., $B$). Fixing any second operand ($B$), we now apply the foregoing argument to $P'$ (looking at arbitrary choices of the first operand).

The original abstract

In this talk I will present a framework for designing worst-case to average-case reductions. Focusing on the problem of Matrix Multiplication, I will describe a transformation that takes any weak algorithm that is only correct on a small fraction of the inputs, and converts it into an algorithm that is correct on all inputs, while paying only a small overhead in running time

Back to list of Oded's choices.