Exponential quantum speedup for ${\mathbb{F}}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

Robin Kothari, Tony Metger, Ryan O'Donnell +2

We study vector subset sum over ${\mathbb{F}}_3^n$: given $m$ random vectors from ${\mathbb{F}}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it i…