1 citations · 2 across the 5 of their papers we have counts for
Showing 2022Show 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
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all Norms
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami +1
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any co…
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…