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.

- 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.
- 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.

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.