1 citations · 2 across the 5 of their papers we have counts for
11 papers
Lattices with Large Kissing Number from Local Density
Huck Bennett, Minki Hhan, Zihan Li +1
Let denote the maximum kissing number of a lattice . We prove that for all and that $κ_p(n) \geq Ω…
Topological -metrics
Willow Barkan-Vered, Huck Bennett, Amir Nayyeri
Metric spaces are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships between points .…
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-…
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…
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…
Improved Hardness of BDD and SVP Under Gap-(S)ETH
Huck Bennett, Chris Peikert, Yi Tang
We show improved fine-grained hardness of two key lattice problems in the norm: Bounded Distance Decoding to within an factor of the minimum distance ($\mathrm{BDD}_{p…
Reconstructing weighted voting schemes from partial information about their power indices
Huck Bennett, Anindya De, Rocco A. Servedio +1
A number of recent works [Goldberg 2006; O'Donnell and Servedio 2011; De, Diakonikolas, and Servedio 2017; De, Diakonikolas, Feldman, and Servedio 2014] have considered the problem…
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…
Fine-grained hardness of CVP(P) -- Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev +1
We show a number of fine-grained hardness results for the Closest Vector Problem in the norm (), and its approximate and non-uniform variants. First, we sh…
On the Quantitative Hardness of CVP
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
$ \newcommand{\eps}{\varepsilon} \newcommand{\problem}[1]{\ensuremath{\mathrm{#1}} } \newcommand{\CVP}{\problem{CVP}} \newcommand{\SVP}{\problem{SVP}} \newcommand{\CVPP}{\problem{C…
On the Lattice Distortion Problem
Huck Bennett, Daniel Dadush, Noah Stephens-Davidowitz
We introduce and study the \emph{Lattice Distortion Problem} (LDP). LDP asks how "similar" two lattices are. I.e., what is the minimal distortion of a linear bijection between the…