Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}$-CVP is shown to be NP-hard, then the polynomial hierarchy collapses.

This seems to imply that, if the polynomial hierarchy does not collapse, we could not hope to show that $n/\alpha$-CVP is NP-hard, meaning that Regev's reduction cannot show that a poly-time LWE algorithm implies $NP\subseteq BQP$. Is that true?

If so, is there some sort of no-go theorem the other way? That is, maybe we want to come up with a better reduction. But if $\sqrt{n/\log n}$-CVP could solve LWE, then we can't hope to reduce LWE to $O(1)$-CVP or else we would show that $\sqrt{n/\log n}$-CVP is NP-hard, again collapsing the polynomial hierarchy. Is this also true? What is the maximum approximation factor of CVP that can still solve LWE?

(and of course, similar questions apply to the classical reduction).

  • $\begingroup$ It's possible for something to be NP-hard for some parameters and not NP-hard for others. Just a guess here... $\endgroup$ – Yehuda Lindell Apr 23 at 15:53
  • $\begingroup$ Right, so the parameters of LWE are the prime, the noise distribution, and number of samples? Regev's reduction works for basically any of them within a certain range I thought. $\endgroup$ – Sam Jaques Apr 24 at 12:05
  • $\begingroup$ I don't mean those parameters. I mean the approximation factor. $\endgroup$ – Yehuda Lindell Apr 25 at 20:35
  • $\begingroup$ Right, by $\gamma$-CVP I meant an approximation factor of $\gamma$. It seems like the transition between NP-hard approximation factors and not NP-hard is between $O(1)$ and $\sqrt{n/\log n}$, from the results mentioned above. But it seems like this excludes LWE from being NP-hard. $\endgroup$ – Sam Jaques Apr 27 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.