Suppose there is an oracle $\mathcal{O}$ that computes a tiny fraction of the entries of the product of two uniformly random binary matrices over integers. We prove that there is a nearly linear-size randomized $\mathcal{O}$-oracle circuit that, with high probability, computes all the entries of the product of every pair ... more >>>

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the \emph{proximity-gaps property} up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction (typically at most $\operatorname{poly}(n)/q$) of \emph{exceptional coefficients} ... more >>>

We show that the nearest-codeword and minimum-distance problems for linear codes over every fixed finite field are W[1]-hard to approximate within any constant factor under deterministic fixed-parameter many-one reductions. This gives unconditional deterministic parameterized inapproximability for minimum distance, including the binary problem usually called Even Set. The reduction starts from ... more >>>