Prange's information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any $\mathbb{F}_2$-linear code $C$ of message length $n$ up to relative error rate $O(\log n / n)$ in $\poly(n)$ time. We show that the error rate can be improved to $O((\log n)^2 / ... more >>>

Given an integer-valued function $f:\{0,1\}^n\rightarrow \{0,1,\dots, m-1\}$ that is mildly hard to compute on instances drawn from some distribution $D$ over $\{0,1\}^n$, we show that the function $g(x_1, \dots, x_t) = f(x_1) + \dots + f(x_t)$ is strongly hard to compute on instances $(x_1, \dots, x_t)$ drawn from the product ... more >>>