1 citations · 1 across the 2 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022★ 1 cited
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
cs.CC2022
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
Huck Bennett, Chris Peikert
We give a simple proof that the (approximate, decisional) Shortest Vector Problem is $\NP$-hard under a randomiz…
cs.CC2020
Hardness of Bounded Distance Decoding on Lattices in Norms
Huck Bennett, Chris Peikert
$ \newcommand{\Z}{\mathbb{Z}} \newcommand{\eps}{\varepsilon} \newcommand{\cc}[1]{\mathsf{#1}} \newcommand{\NP}{\cc{NP}} \newcommand{\problem}[1]{\mathrm{#1}} \newcommand{\BDD}{\pro…